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 
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/
@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},
     year = {2009},
     volume = {17},
     number = {1},
     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
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
%U http://geodesic.mathdoc.fr/item/TIMB_2009_17_1_a10/
%G ru
%F TIMB_2009_17_1_a10

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.

[1] Bodlaender H.L., Kloks T., Tan R.B., van Leeuwen J., “Approximations for $\lambda$-Coloring of Graphs”, The Computer Journal, 47:2 (2004), 193–204 | DOI | MR | Zbl

[2] Bodlaender H.L., Kloks T., Tan R.B., van Leeuwen J., $\lambda$-Coloring of graphs, Tech Report, Dept. of Computer Science, Utrecht University, 1999

[3] Fiala J., Kloks T., Kratochvil J., “Fixed-Parameter Complexity of $\lambda$-Labelings”, Lecture Notes in Computer Science, 1665, 1999, 350–363 | MR | Zbl

[4] Korshunov A.D., “Osnovnye svoistva sluchainykh grafov s bolshim chislom vershin i reber”, Uspekhi mat. nauk, 40:1 (1985), 107–173 | MR | Zbl

[5] Griggs J.R., Yeh R.K., “Labelling graphs with a condition at distance 2”, SIAM Journal of Discreet Mathematics, 5:4 (1992), 586–595 | DOI | MR | Zbl

[6] Yeh R.K., Labelling graphs with a condition at distance two, Ph. D. Thesis, Department of Mathematics, University of South Carolina, 1990

[7] Yeh R.K., “A syrvey on labelling graphs with a condition at distance two”, Discreet Mathematics, 306 (2006), 1217–1231 | DOI | MR | Zbl

[8] Calamoneri T., Petrechi R., “$\lambda$-Coloring matrogenic graphs”, Discrete Applied Mathematics, 154 (2006), 2445–2457 | DOI | MR | Zbl

[9] Mahadev N.V.R., Peled U.N., Threshold Graphs and Related Topics, Annals of Discrete Mathhematics, 56, Elsevier, 1995 | MR | Zbl

[10] Maksimovich O.V., Tyshkevich R.I., “Normalnaya forma dominantno-porogovogo grafa”, Dokl. NAN Belarusi, 53:2 (2009), 16–18 | MR

[11] Tyshkevich R.I., Chernyak A.A., “Dekompozitsiya grafov”, Kibernetika, 1985, no. 2, 67–74 | MR