A sequence of symbols
… is called
if it does not contain a subsequence of consecutive terms of the form
. A century ago Thue showed that there exist arbitrarily long square-free sequences using only three symbols. Sequences can be thought of as colors on the vertices of a path. Following the paper of Alon, Grytczuk, Hałuszczak and Riordan, we examine graph colorings for which the color sequence is square-free on any path. The main result is that the vertices of any
-tree have a coloring of this kind using
) colors if
> 6. Alon et al. conjectured that a fixed number of colors suffices for any planar graph. We support this conjecture by showing that this number is at most 12 for outerplanar graphs. On the other hand we prove that some outerplanar graphs require at least 7 colors. Using this latter we construct planar graphs, for which at least 10 colors are necessary.
Authors:János Barát, Péter Hajnal, Yixun Lin and Aifeng Yang
Kinnersley and Langston used a computer search to characterize the class of graphs with path-width at most two. The excluded minor list consists of 110 graphs. This set is fairly large, and the list gives little insight to structural properties of the targeted graph class. We take a different route here. We concentrate on the building blocks of the graphs with path-width at most two and how they are glued together. In this way, we get a short and compact characterization of 2-connected and 2-edge-connected graphs with path-width at most two.