In the mathematical

Mathematics

Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...

 area of graph theory

Graph theory

In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...

, the Thue number of a graph is a variation of the chromatic index, defined by Alon et al. (2002) and named by them after mathematician Axel Thue

Axel Thue

Axel Thue was a Norwegian mathematician, known for highly original work in diophantine approximation, and combinatorics....

, who studied the squarefree words used to define this number.

Alon et al. define a nonrepetitive coloring of a graph to be an assignment of colors to the edges of the graph, such that there does not exist any even-length simple path

Path (graph theory)

In graph theory, a path in a graph is a sequence of vertices such that from each of its vertices there is an edge to the next vertex in the sequence. A path may be infinite, but a finite path always has a first vertex, called its start vertex, and a last vertex, called its end vertex. Both of them...

 in the graph in which the colors of the edges in the first half of the path form the same sequence as the colors of the edges in the second half of the path. The Thue number of a graph is the minimum number of colors needed in any nonrepetitive coloring.

Variations on this concept involving vertex colorings or more general walks on a graph have been studied by several authors including Barát and Varjú, Barát and Wood (2005), Brešar and Klavžar (2004), and Kündgen and Pelsmajer.

Example

Consider a pentagon

Pentagon

In geometry, a pentagon is any five-sided polygon. A pentagon may be simple or self-intersecting. The sum of the internal angles in a simple pentagon is 540°. A pentagram is an example of a self-intersecting pentagon.- Regular pentagons :In a regular pentagon, all sides are equal in length and...

, that is, a cycle

Cycle graph

In graph theory, a cycle graph or circular graph is a graph that consists of a single cycle, or in other words, some number of vertices connected in a closed chain. The cycle graph with n vertices is called Cn...

 of five vertices. If we color the edges with two colors, some two adjacent edges will have the same color x; the path formed by those two edges will have the repetitive color sequence xx. If we color the edges with three colors, one of the three colors will be used only once; the path of four edges formed by the other two colors will either have two consecutive edges or will form the repetitive color sequence xyxy. However, with four colors it is not difficult to avoid all repetitions. Therefore, the Thue number of C₅ is four.

Results

Alon et al. use the Lovász local lemma

Lovász local lemma

In probability theory, if a large number of events are all independent of one another and each has probability less than 1, then there is a positive probability that none of the events will occur...

 to prove that the Thue number of any graph is at most quadratic in its maximum degree; they provide an example showing that for some graphs this quadratic dependence is necessary. In addition they show that the Thue number of a path of four or more vertices is exactly three, and that the Thue number of any cycle is at most four, and that the Thue number of the Petersen graph

Petersen graph

In the mathematical field of graph theory, the Petersen graph is an undirected graph with 10 vertices and 15 edges. It is a small graph that serves as a useful example and counterexample for many problems in graph theory. The Petersen graph is named for Julius Petersen, who in 1898 constructed it...

 is exactly five.

The known cycles with Thue number four are C₅, C₇, C₉, C₁₀, C₁₄, and C₁₇. Alon et al. conjecture that the Thue number of any larger cycle is three; they verified computationally that the cycles listed above are the only ones of length ≤ 2001 with Thue number four. Currie resolved this in a 2002 paper, showing that all cycles with 18 or more vertices have Thue number 3.

Computational complexity

Testing whether a coloring has a repetitive path is in NP, so testing whether a coloring is nonrepetitive is in co-NP, and Manin showed that it is co-NP-complete. The problem of finding such a coloring belongs to in the polynomial hierarchy

Polynomial hierarchy

In computational complexity theory, the polynomial hierarchy is a hierarchy of complexity classes that generalize the classes P, NP and co-NP to oracle machines...

, and again Manin showed that it is complete for this level.