Avoiding large squares in trees and planar graphs - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Accéder directement au contenu
Pré-Publication, Document De Travail Année : 2021

Avoiding large squares in trees and planar graphs

Résumé

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 et versions

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

Identifiants

Citer

Daniel Gonçalves, Pascal Ochem, Matthieu Rosenfeld. Avoiding large squares in trees and planar graphs. 2021. ⟨lirmm-03452602⟩
34 Consultations
0 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More