Improved 2-Distance Coloring of Planar Graphs with Maximum Degree 5

2023/07/31 by Aoki, Kengo · 4 citations
#05C15 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2307.16394

Abstract

A 2-distance k-coloring of a graph G is a proper k-coloring such that any two vertices at distance two or less get different colors. The 2-distance chromatic number of G is the minimum k such that G has a 2-distance k-coloring, denote as χ₂(G). In this paper, we show that χ₂(G) ≤ 17 for every planar graph G with maximum degree Δ≤ 5, which improves a former bound χ₂(G) ≤ 18.

Cited by

• List Coloring of the Square of 4-Irregular Graphs
• 2-Distance Coloring of Planar Graphs with Maximum Degree at Least 6
• The square of every subcubic planar graph without 4-cycles and 5-cycles is 7-choosable
• S-packing chromatic critical graphs

Related

• 2-distance 20-coloring of planar graphs with maximum degree 6
• A 2-distance (2Δ+7)-coloring of planar graphs
• An improved bound for 2-distance coloring of planar graphs with girth six
• On 2-distance 16-coloring of planar graphs with maximum degree at most five
• 2-Distance Coloring of Planar Graphs with Maximum Degree at Least 6