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

2021/03/22 by Hoang La, La, Hoang, Mickael Montassier +1 · 3 citations
Computer Science · Mathematics · #05C15 #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #cs.DM #math.CO #msc:05C15

paper · pdf · doi:10.48550/arxiv.2103.11687

26 pages, 17 figures

arxiv created 2021/04/03 · arxiv updated 2021/04/06

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 (Δ+1)-coloring for graphs with maximum average degree less than (18)/(7) and maximum degree Δ≥ 7. As a corollary, every planar graph with girth at least 9 and Δ≥ 7 admits a 2-distance (Δ+1)-coloring. The proof uses the potential method to reduce new configurations compared to classic approaches on 2-distance coloring.

Cited by

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

Related

• 2-distance (Δ+2)-coloring of sparse graphs
• 2-distance list (Δ+ 3)-coloring of sparse graphs
• A 2-distance (2Δ+7)-coloring of planar graphs
• Some results on 2-distance coloring of planar graphs with girth five
• Improved 2-Distance Coloring of Planar Graphs with Maximum Degree 5