Geodesic
Injective $L(2,1)$-coloring as an optimization problem on the set of permutations of graph vertices: domishold graphs
Trudy Instituta matematiki, Tome 17 (2009) no. 1, pp. 110-118

Voir la notice de l'article provenant de la source Math-Net.Ru

The class of domishold graphs is a nearest extension of a well-studied class of threshold graphs. A linear algorithm for optimal $L(2,1)$-colouring of threshold graphs is known. In this paper we consider the injective $L(2,1)$ colouring problem. This problem is very close to the original $L(2,1)$-coloring, more over for almost all graphs they coincide. We introduce the new interpretation of the injective $L(2,1)$ colouring problem as an optimization problem on the set of permutations of graph vertices. Based on this interpretation and using the decomposition of domishold graphs we present an optimal algorithm that colours domishold graphs in the $O(n+m)$ time and remains linear in $n$ for threshold graphs. 
@article{TIMB_2009_17_1_a10,
     author = {O. V. Maksimovich and R. I. Tyshkevich},
     title = {Injective $L(2,1)$-coloring as an optimization problem on the set of permutations of graph vertices: domishold graphs},
     journal = {Trudy Instituta matematiki},
     pages = {110--118},
     publisher = {mathdoc},
     volume = {17},
     number = {1},
     year = {2009},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/TIMB_2009_17_1_a10/}
}
TY  - JOUR
AU  - O. V. Maksimovich
AU  - R. I. Tyshkevich
TI  - Injective $L(2,1)$-coloring as an optimization problem on the set of permutations of graph vertices: domishold graphs
JO  - Trudy Instituta matematiki
PY  - 2009
SP  - 110
EP  - 118
VL  - 17
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/TIMB_2009_17_1_a10/
LA  - ru
ID  - TIMB_2009_17_1_a10
ER  - 
%0 Journal Article
%A O. V. Maksimovich
%A R. I. Tyshkevich
%T Injective $L(2,1)$-coloring as an optimization problem on the set of permutations of graph vertices: domishold graphs
%J Trudy Instituta matematiki
%D 2009
%P 110-118
%V 17
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/TIMB_2009_17_1_a10/
%G ru
%F TIMB_2009_17_1_a10
O. V. Maksimovich; R. I. Tyshkevich. Injective $L(2,1)$-coloring as an optimization problem on the set of permutations of graph vertices: domishold graphs. Trudy Instituta matematiki, Tome 17 (2009) no. 1, pp. 110-118. http://geodesic.mathdoc.fr/item/TIMB_2009_17_1_a10/