2-distance (Δ+2)-coloring of sparse graphs

2021/09/24 by Hoang La, La, Hoang, Mickael Montassier +2 · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Limits and Structures in Graph Theory #cs.DM #math.CO

paper · pdf · doi:10.48550/arxiv.2109.11927

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

arxiv created 2021/09/24 · openalex publication_date 2021/09/24 · arxiv updated 2021/09/27 · openalex created_date 2021/10/11 · openalex updated_date 2026/07/28

Abstract

A 2-distance k-coloring of a graph is a proper k-coloring of the vertices where vertices at distance at most 2 cannot share the same color. We prove the existence of a 2-distance (Δ+2)-coloring for graphs with maximum average degree less than (8)/(3) (resp. (14)/(5)) and maximum degree Δ≥ 6 (resp. Δ≥ 10). As a corollary, every planar graph with girth at least 8 (resp. 7) and maximum degree Δ≥ 6 (resp. Δ≥ 10) admits a 2-distance (Δ+2)-coloring.

Citations

• r-hued (r+1)-coloring of planar graphs with girth at least 8 for r≥9
• 2-distance list (Δ+ 3)-coloring of sparse graphs
• 2-distance (Δ+1)-coloring of sparse graphs using the potential method

Cited by

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

Related

• 2-distance (Δ+1)-coloring of sparse graphs using the potential method
• 2-distance list (Δ+ 3)-coloring of sparse graphs
• A 2-distance (2Δ+7)-coloring of planar graphs
• 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