Avoiding large squares in trees and planar graphs - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Preprints, Working Papers, ... Year : 2021

Avoiding large squares in trees and planar graphs

Abstract

The Thue number $\pi(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$, $\pi(C)$ is the supremum of $\pi(G)$ over the graphs $G\in C$. The Thue number has been investigated for famous minor-closed classes: $\pi(tree)=4$, $7\le\pi(outerplanar)\le12$, and $11\le\pi(planar)\le768$. Following a suggestion of Grytczuk, we consider the generalized parameters $\pi_k(C)$ such that only squares of period at least $k$ must be avoided. Thus, $\pi(C)=\pi_1(C)$. We show that $\pi_5(tree)=2$, $\pi_2(tree)=3$, and $\pi_k(planar)\ge11$ for every fixed $k$.

Dates and versions

lirmm-03452602 , version 1 (27-11-2021)

Identifiers

Cite

Daniel Gonçalves, Pascal Ochem, Matthieu Rosenfeld. Avoiding large squares in trees and planar graphs. 2021. ⟨lirmm-03452602⟩
34 View
0 Download

Altmetric

Share

Gmail Mastodon Facebook X LinkedIn More