2013/01/29 by Marthe Bonamy, Bonamy, Marthe, Benjamin Lévêque +3
Computer Science · Engineering · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Graph Labeling and Dimension Problems #cs.DM #graph theory and CDMA systems #math.CO
paper · pdf · doi:10.48550/arxiv.1301.7090
22 pages, 5 figures, submitted
arxiv created 2013/01/29 · openalex publication_date 2013/01/29 · arxiv updated 2013/01/31 · openalex created_date 2016/06/24 · openalex updated_date 2026/07/28
For graphs of bounded maximum average degree, we consider the problem of 2-distance coloring. This is the problem of coloring the vertices while ensuring that two vertices that are adjacent or have a common neighbor receive different colors. It is already known that planar graphs of girth at least 6 and of maximum degree D are list 2-distance (D+2)-colorable when D>=24 (Borodin and Ivanova (2009)) and 2-distance (D+2)-colorable when D>=18 (Borodin and Ivanova (2009)). We prove here that D>=17 suffices in both cases. More generally, we show that graphs with maximum average degree less than 3 and D>=17 are list 2-distance (D+2)-colorable. The proof can be transposed to list injective (D+1)-coloring.