Avoiding large squares in trees and planar graphs

Abstract: The Thue number

p i (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

,

p i (C)

is the supremum of

p i (G)

over the graphs

G i n C

. The Thue number has been investigated for famous minor-closed classes:

p i (t r e e) = 4

,

7 l e p i (o u t e r p l a n a r) l e 12

, and

11 l e p i (p l a n a r) l e 768

. Following a suggestion of Grytczuk, we consider the generalized parameters

p i_{k} (C)

such that only squares of period at least

k

must be avoided. Thus,

p i (C) = p i_{1} (C)

. We show that

p i_{5} (t r e e) = 2

,

p i_{2} (t r e e) = 3

, and

p i_{k} (p l a n a r) g e 11

for every fixed

k

.

This page was built for publication: Avoiding large squares in trees and planar graphs