Thue number

Last updated
The Thue number of the 5-cycle is four. Thue-number.svg
The Thue number of the 5-cycle is four.

In the mathematical area of graph theory, the Thue number of a graph is a variation of the chromatic index, defined by Alon et al. (2002) and named after mathematician Axel Thue, who studied the squarefree words used to define this number.

Contents

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 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, that is, a cycle 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 C5 is four.

Results

Alon et al. use the Lovász local lemma 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 is exactly five.

The known cycles with Thue number four are C5, C7, C9, C10, C14, and C17. 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, and again Manin showed that it is complete for this level.

Related Research Articles

Graph coloring Assignment of colors to elements of a graph subject to certain constraints.

In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices of a graph such that no two adjacent vertices are of the same color; this is called a vertex coloring. Similarly, an edge coloring assigns a color to each edge so that no two adjacent edges are of the same color, and a face coloring of a planar graph assigns a color to each face or region so that no two faces that share a boundary have the same color.

In graph theory, a uniquely colorable graph is a k-chromatic graph that has only one possible (proper) k-coloring up to permutation of the colors. Equivalently, there is only one way to partition its vertices into k independent sets and there is no way to partition them into k−1 independent sets.

Edge coloring

In graph theory, an edge coloring of a graph is an assignment of "colors" to the edges of the graph so that no two incident edges have the same color. For example, the figure to the right shows an edge coloring of a graph by the colors red, blue, and green. Edge colorings are one of several different types of graph coloring. The edge-coloring problem asks whether it is possible to color the edges of a given graph using at most k different colors, for a given value of k, or with the fewest possible colors. The minimum required number of colors for the edges of a given graph is called the chromatic index of the graph. For example, the edges of the graph in the illustration can be colored by three colors but cannot be colored by two colors, so the graph shown has chromatic index three.

In graph theory, a branch of mathematics, list coloring is a type of graph coloring where each vertex can be restricted to a list of allowed colors. It was first studied in the 1970s in independent papers by Vizing and by Erdős, Rubin, and Taylor.

Exact coloring

In graph theory, an exact coloring is a (proper) vertex coloring in which every pair of colors appears on exactly one pair of adjacent vertices. That is, it is a partition of the vertices of the graph into disjoint independent sets such that, for each pair of distinct independent sets in the partition, there is exactly one edge with endpoints in each set.

In graph theory, Vizing's theorem states that every simple undirected graph may be edge colored using a number of colors that is at most one larger than the maximum degree Δ of the graph. At least Δ colors are always necessary, so the undirected graphs may be partitioned into two classes: "class one" graphs for which Δ colors suffice, and "class two" graphs for which Δ + 1 colors are necessary. A more general version of Vizing's theorem states that every undirected multigraph without loops can be colored with at most Δ+µ colors, where µ is the multiplicity of the multigraph. The theorem is named for Vadim G. Vizing who published it in 1964.

Triangle-free graph

In the mathematical area of graph theory, a triangle-free graph is an undirected graph in which no three vertices form a triangle of edges. Triangle-free graphs may be equivalently defined as graphs with clique number ≤ 2, graphs with girth ≥ 4, graphs with no induced 3-cycle, or locally independent graphs.

Hedetniemis conjecture Conjecture in graph theory

In graph theory, Hedetniemi's conjecture, formulated by Stephen T. Hedetniemi in 1966, concerns the connection between graph coloring and the tensor product of graphs. This conjecture states that

Median graph

In graph theory, a division of mathematics, a median graph is an undirected graph in which every three vertices a, b, and c have a unique median: a vertex m(a,b,c) that belongs to shortest paths between each pair of a, b, and c.

Tietzes graph

In the mathematical field of graph theory, Tietze's graph is an undirected cubic graph with 12 vertices and 18 edges. It is named after Heinrich Franz Friedrich Tietze, who showed in 1910 that the Möbius strip can be subdivided into six regions that all touch each other – three along the boundary of the strip and three along its center line – and therefore that graphs that are embedded onto the Möbius strip may require six colors. The boundary segments of the regions of Tietze's subdivision form an embedding of Tietze's graph.

Star coloring

In graph-theoretic mathematics, a star coloring of a graph G is a (proper) vertex coloring in which every path on four vertices uses at least three distinct colors. Equivalently, in a star coloring, the induced subgraphs formed by the vertices of any two colors has connected components that are star graphs. Star coloring has been introduced by Grünbaum (1973). The star chromatic number of G is the fewest colors needed to star color G.

Greedy coloring

In the study of graph coloring problems in mathematics and computer science, a greedy coloring or sequential coloring is a coloring of the vertices of a graph formed by a greedy algorithm that considers the vertices of the graph in sequence and assigns each vertex its first available color. Greedy colorings can be found in linear time, but they do not in general use the minimum number of colors possible.

In graph theory, a perfectly orderable graph is a graph whose vertices can be ordered in such a way that a greedy coloring algorithm with that ordering optimally colors every induced subgraph of the given graph. Perfectly orderable graphs form a special case of the perfect graphs, and they include the chordal graphs, comparability graphs, and distance-hereditary graphs. However, testing whether a graph is perfectly orderable is NP-complete.

In graph theory, a branch of mathematics, a crown graph on 2n vertices is an undirected graph with two sets of vertices {u1, u2, ..., un} and {v1, v2, ..., vn} and with an edge from ui to vj whenever i ≠ j.

Apollonian network

In combinatorial mathematics, an Apollonian network is an undirected graph formed by a process of recursively subdividing a triangle into three smaller triangles. Apollonian networks may equivalently be defined as the planar 3-trees, the maximal planar chordal graphs, the uniquely 4-colorable planar graphs, and the graphs of stacked polytopes. They are named after Apollonius of Perga, who studied a related circle-packing construction.

In graph theory, a branch of mathematics, the Hajós construction is an operation on graphs named after György Hajós (1961) that may be used to construct any critical graph or any graph whose chromatic number is at least some given threshold.

Gallai–Hasse–Roy–Vitaver theorem

In graph theory, the Gallai–Hasse–Roy–Vitaver theorem is a form of duality between the colorings of the vertices of a given undirected graph and the orientations of its edges. It states that the minimum number of colors needed to properly color any graph G equals one plus the length of a longest path in an orientation of G chosen to minimize this path's length. The orientations for which the longest path has minimum length always include at least one acyclic orientation.

Graph power

In graph theory, a branch of mathematics, the kth powerGk of an undirected graph G is another graph that has the same set of vertices, but in which two vertices are adjacent when their distance in G is at most k. Powers of graphs are referred to using terminology similar to that of exponentiation of numbers: G2 is called the square of G, G3 is called the cube of G, etc.

Distinguishing coloring

In graph theory, a distinguishing coloring or distinguishing labeling of a graph is an assignment of colors or labels to the vertices of the graph that destroys all of the nontrivial symmetries of the graph. The coloring does not need to be a proper coloring: adjacent vertices are allowed to be given the same color. For the colored graph, there should not exist any one-to-one mapping of the vertices to themselves that preserves both adjacency and coloring. The minimum number of colors in a distinguishing coloring is called the distinguishing number of the graph.

Well-colored graph

In graph theory, a subfield of mathematics, a well-colored graph is an undirected graph for which greedy coloring uses the same number of colors regardless of the order in which colors are chosen for its vertices. That is, for these graphs, the chromatic number and Grundy number are equal.

References