Improved square coloring of planar graphs

2021/12/23 by Nicolás Bousquet, Bousquet, Nicolas, Quentin Deschamps +5 · 3 citations
Computer Science · #Advanced Graph Theory Research #Graph Labeling and Dimension Problems #Computational Geometry and Mesh Generation

paper · pdf · doi:10.48550/arxiv.2112.12512

Abstract

Square coloring is a variant of graph coloring where vertices within distance two must receive different colors. When considering planar graphs, the most famous conjecture (Wegner, 1977) states that \frac32Δ+1 colors are sufficient to square color every planar graph of maximum degree Δ. This conjecture has been proven asymptotically for graphs with large maximum degree. We consider here planar graphs with small maximum degree and show that 2Δ+7 colors are sufficient, which improves the best known bounds when 6\leqslant Δ\leqslant 31.

Cited by

• List Coloring of the Square of 4-Irregular Graphs
• Improved bounds of r-hued colorings of planar graphs
• 2-Distance Coloring of Planar Graphs with Maximum Degree at Least 6

Related

• Coloring squares of planar graphs with small maximum degree
• Square Coloring of Planar Graphs with Maximum Degree at Most Five
• Relaxation of Wegner's Planar Graph Conjecture for maximum degree 4
• List Colouring Squares of Planar Graphs
• Improved bounds of r-hued colorings of planar graphs