2-distance list (Δ+2)-coloring of planar graphs with girth at least 10

2021/09/29 by Hoang La, La, Hoang, Mickael Montassier +2
Arts and Humanities · Computer Science · Mathematics · Social Sciences · #Combinatorics (math.CO) #Crafts, Textile, and Design #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Urban Planning and Governance #cs.DM #math.CO

paper · pdf · doi:10.48550/arxiv.2109.14499

14 pages, 13 figures. arXiv admin note: substantial text overlap with arXiv:2106.03587, arXiv:2103.11687, arXiv:2105.01684, arXiv:2109.11927

arxiv created 2021/09/29 · openalex publication_date 2021/09/29 · arxiv updated 2021/09/30 · openalex created_date 2022/10/02 · openalex updated_date 2026/07/28

Abstract

Given a graph G and a list assignment L(v) for each vertex of v of G. A proper L-list-coloring of G is a function that maps every vertex to a color in L(v) such that no pair of adjacent vertices have the same color. We say that a graph is list k-colorable when every vertex v has a list of colors of size at least k. A 2-distance coloring is a coloring where vertices at distance at most 2 cannot share the same color. We prove the existence of a 2-distance list (Δ+2)-coloring for planar graphs with girth at least 10 and maximum degree Δ≥ 4.

Citations

• 2-distance (Δ+1)-coloring of sparse graphs using the potential method
• 2-distance list (Δ+ 3)-coloring of sparse graphs
• 2-distance (Δ+2)-coloring of sparse graphs

Related

• Graphs with maximum degree D at least 17 and maximum average degree less than 3 are list 2-distance (D+2)-colorable
• On 2-Distance (Δ+4)-coloring of planar graphs with girth at least five
• Some results on 2-distance coloring of planar graphs with girth five
• An improved bound for 2-distance coloring of planar graphs with girth six
• 2-distance (Δ+2)-coloring of sparse graphs