Simple Search

Query:

Enter a query and click »Search«...

Format:

Display: entries per page entries

Zbl 1164.05021
Barát, János; Varjú, Péter P.
On square-free vertex colorings of graphs. (English)
[J] Stud. Sci. Math. Hung. 44, No. 3, 411-422 (2007). ISSN 0081-6906; ISSN 1588-2896/e

A sequence of symbols is called square-free if it does not contain a subsequence of the form $x_1,\dots,x_m,x_1,\dots,x_m$. {\it Thue} proved that there is an infinite square-free sequence consisting of three symbols. Sequences can be thought of as colours on the vertices of a path. The authors examine graph colourings for which the colour sequence is square-free on any path. They obtain the result that the vertices of any $k$-tree have a colouring of this kind using $O(c^k)$ colours if $c>6$. Moreover, they support the conjecture of {\it Alon et al.} that a fixed number of colours suffices for any planar graph. They show that this number is at most 12 for outerplanar graphs and construct some outerplanar graphs which require at least 7 colours. Moreover, they construct planar graphs for which at least 10 colours are needed.
[Ulrike Baumann (Dresden)]

MSC 2000:: *05C15 Chromatic theory of graphs and maps

Keywords: graph colouring; Thue sequence; outerplanar graph

Comment on this Item PDF MathML XML ASCII DVI PS BibTeX Online Ordering Article Journal

	Scientific prize winners of the ICM 2010
	Overhang
	Lie groups, physics and geometry. An introduction for physicists, engineers and chemists.

Simple Search

Zentralblatt MATH Berlin [Germany]