Avoiding large squares in trees and planar graphs

2021/06/03 by Gonçalves, Daniel, Ochem, Pascal, Rosenfeld, Matthieu
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2106.01521

Abstract

The Thue number π(G) of a graph G is the minimum number of colors needed to color G without creating a square on a path of G. For a graph class C, π(C) is the supremum of π(G) over the graphs G∈ C. The Thue number has been investigated for famous minor-closed classes: π(tree)=4, 7≤π(outerplanar)≤12, and 11≤π(planar)≤768. Following a suggestion of Grytczuk, we consider the generalized parameters π_k(C) such that only squares of period at least k must be avoided. Thus, π(C)=π₁(C). We show that π₅(tree)=2, π₂(tree)=3, and π_k(planar)≥11 for every fixed k.

Related

• Coloring squares of planar graphs with small maximum degree
• On New Thue Colouring Concepts of Certain Graphs
• Improved square coloring of planar graphs
• Square Coloring of Planar Graphs with Maximum Degree at Most Five
• List Colouring Squares of Planar Graphs