2-Distance Colorings of Integer Distance Graphs

Benmedjdoub, Brahim ; Bouchemakh, Isma ; Sopena, Éric

Discussiones Mathematicae. Graph Theory, Tome 39 (2019) no. 2, pp. 589-603.

Résumé

A 2-distance k-coloring of a graph G is a mapping from V (G) to the set of colors 1,. . ., k such that every two vertices at distance at most 2 receive distinct colors. The 2-distance chromatic number χ₂(G) of G is then the smallest k for which G admits a 2-distance k-coloring. For any finite set of positive integers D = d₁, . . ., d_ℓ, the integer distance graph G = G(D) is the infinite graph defined by V (G) = ℤ and uv ∈ E(G) if and only if |v − u| ∈ D. We study the 2-distance chromatic number of integer distance graphs for several types of sets D. In each case, we provide exact values or upper bounds on this parameter and characterize those graphs G(D) with χ₂(G(D)) = ∆(G(D)) + 1.

Détail

Keywords: 2-distance coloring, integer distance graph

Bibliographie

[1] G. Agnarsson and M.M. Halldórsson, Coloring powers of planar graphs, SIAM J. Discrete Math. 16 (2003) 651–662. doi:10.1137/S0895480100367950

[2] M. Bonamy, B. Lévêque and A. Pinlou, 2 -distance coloring of sparse graphs, J. Graph Theory 77 (2014) 190–218. doi:10.1002/jgt.21782

[3] M. Bonamy, B. Lévêque and A. Pinlou, Graphs with maximum degree ∆ ≥ 17 and maximum average degree less than 3 are list 2 -distance (∆ + 2) -colorable, Discrete Math. 317 (2014) 19–32. doi:10.1016/j.disc.2013.10.022

[4] O.V. Borodin and A.O. Ivanova, 2 -distance (∆ + 2) -coloring of planar graphs with girth six and ∆ ≥ 18, Discrete Math. 309 (2009) 6496–6502. doi:10.1016/j.disc.2009.06.029

[5] T. Calamoneri, The L ( h, k ) -labelling problem: An updated survey and annotated bibliography, Comput. J. 54 (2011) 1344-1371. doi:10.1093/comjnl/bxr037

[6] Z. Dvořák, D. Král, P. Nejedlý and R. Škrekovski, Coloring squares of planar graphs with girth six, European J. Combin. 29 (2008) 838–849. doi:10.1016/j.ejc.2007.11.005

[7] A. Kemnitz and H. Kolberg, Coloring of integer distance graphs, Discrete Math. 191 (1998) 113–123. doi:10.1016/S0012-365X(98)00099-5

[8] F. Kramer and H. Kramer, Un probleme de coloration des sommets d’un graphe, C. R. Acad. Sci. Paris A 268 (1969) 46–48.

[9] F. Kramer and H. Kramer, A survey on the distance-colouring of graphs, Discrete Math. 308 (2008) 422–426. doi:10.1016/j.disc.2006.11.059

[10] K.-W. Lih and W.-F. Wang, Coloring the square of an outerplanar graph, Taiwanese J. Math. 10 (2006) 1015–1023. doi:10.11650/twjm/1500403890

[11] D.D.-F. Liu, From rainbow to the lonely runner: A survey on coloring parameters of distance graphs, Taiwanese J. Math. 12 (2008) 851–871. doi:10.11650/twjm/1500404981

[12] M. Voigt, Über die chromatische Zahl einer speziellen Klasse unendlicher Graphen, Ph.D. Thesis (Techn. Univ. Ilmenau, 1992).

[13] H. Walther, Über eine spezielle Klasse unendlicher Graphen, in: Graphentheorie, K. Wagner and R. Bodendiek (Ed(s)), (Bibl. Inst., Mannheim, 1990) 2, 268–295.

[14] W.-F. Wang and K.-W. Lih, Labeling planar graphs with conditions on girth and distance two, SIAM J. Discrete Math. 17 (2003) 264-275. doi:10.1137/S0895480101390448

[15] G. Wegner, Graphs with given diameter and a coloring problem (Technical Report, University of Dortmund, 1977). doi:10.17877/DE290R-16496

[16] X. Zhu, Circular chromatic number of distance graphs with distance sets of cardinality 3, J. Graph Theory 41 (2002) 195–207. doi:10.1002/jgt.10062