Square Coloring of Planar Graphs with Maximum Degree at Most Five

2023/08/03 by Zou, Jiani, Han, Miaomiao, Lai, Hong-Jian · 3 citations
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2308.01824

Abstract

The square of a graph G, denoted by G², is obtained from G by adding an edge to connect every pair of vertices with a common neighbor in G. In this paper we prove that for every planar graph G with maximum degree at most 5, G² admits a proper vertex coloring using at most 17 colors, which improves the upper bound 18 recently obtained by Hou, Jin, Miao, and Zhao.

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

Related

• Improved square coloring of planar graphs
• Coloring squares of planar graphs with small maximum degree
• Relaxation of Wegner's Planar Graph Conjecture for maximum degree 4
• B-colorings of planar and outerplanar graphs
• Equitable Colorings of Planar Graphs without Short Cycles