2-distance 20-coloring of planar graphs with maximum degree 6

2024/06/25 by Kengo Aoki, Aoki, Kengo
Computer Science · Engineering · #05C15 #Advanced Graph Theory Research #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #FOS: Mathematics #graph theory and CDMA systems

paper · pdf · doi:10.48550/arxiv.2406.17191

openalex publication_date 2024/06/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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, denoted by χ₂(G). In this paper, we show that χ₂(G) ≤ 20 for every planar graph G with maximum degree at most six, which improves a former bound χ₂(G) ≤ 21.

Related

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