Thue number

Thue number

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 by them after mathematician Axel Thue, 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 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), and Brešar and Klavžar (2004).

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 "C"5 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 "C"5, "C"7, "C"9, "C"10, "C"14, and "C"17. 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.

Computational complexity

The Thue number is notable for being a simply defined graph invariant the computational complexity of which is open, though it appears syntactically to belong to the second level of the polynomial hierarchy. That is, testing whether a coloring has a repetitive path is in NP, so testing whether a coloring is nonrepetitive is in co-NP, and the problem of finding such a coloring belongs to Sigma_2^P in the polynomial hierarchy. However the Thue number is not known to be complete for this class (Schaefer and Umans 2005).

References

*cite journal
author = Alon, Noga; Grytczuk, Jaroslaw; Hałuszczak, Mariusz; Riordan, Oliver
title = Nonrepetitive colorings of graphs
journal = Random Structures & Algorithms
volume = 21
issue = 3–4
year = 2002
pages = 336–346
doi = 10.1002/rsa.10057
url = http://www.math.tau.ac.il/~nogaa/PDFS/aghr2.pdf

*cite web
author = Barát, János; Varjú, P. P.
title = On square-free edge colorings of graphs
url = http://www.math.u-szeged.hu/~barat/bj_publ/edges.ps

*cite journal
author = Barát, János; Wood, David
title = Notes on nonrepetitive graph colouring
year = 2005
id = arxiv|archive=math.CO|id=0509608

*cite journal
author = Brešar, Boštjan; Klavžar, Sandi
title = Square-free coloring of graphs
journal = Ars Combin.
year = 2004
volume = 70
pages = 3–13

*cite journal
author = Schaefer, Marcus and Umans, Christopher
title = Completeness in the polynomial-time hierarchy: a compendium
year = 2005
url = http://ls2-www.cs.uni-dortmund.de/lehre/winter200506/ktea/papers/phcom.ps


Wikimedia Foundation. 2010.

Игры ⚽ Поможем сделать НИР

Look at other dictionaries:

  • Thue (programming language) — Thue (pronEng|ˈtuːeɪ TOO ay ) is an esoteric programming language invented by John Colagioia in early 2000. It is a meta language that can be used to define or recognize Type 0 languages from the Chomsky hierarchy. Because it is able to define… …   Wikipedia

  • Thue–Morse sequence — See also: Prouhet–Thue–Morse constant 5 logical matrices that give the beginning of the T. M. sequence, when read line by line Either in set A (vertical index) …   Wikipedia

  • Thue-Morse sequence — See also: Thue Morse constantIn mathematics and its applications, the Thue Morse sequence, or Prouhet Thue Morse sequence, is a certain binary sequence whose initial segments alternate (in a certain sense).The Thue Morse sequence begins:0… …   Wikipedia

  • Thue–Siegel–Roth theorem — In mathematics, the Thue–Siegel–Roth theorem, also known simply as Roth s theorem, is a foundational result in diophantine approximation to algebraic numbers. It is of a qualitative type, stating that a given algebraic number α may not have too… …   Wikipedia

  • Thue's theorem — You might be looking for Thue–Siegel–Roth theorem.Thue s theorem is a mathematical theorem first proved by Axel Thue in 1909. [A. Thue, Über Annäherungswerte algebraischer Zahlen , Journal für die reine und angewandte Mathematik, 135, pages 284… …   Wikipedia

  • Semi-Thue-System — (oder auch Umformungssystem, Wortersetzungssystem oder Stringersetzungssystem) ist in der Theoretischen Informatik ein Regelsystem zur Transformation von Wörtern. Im Gegensatz zu formalen Grammatiken liegt aber nur ein Alphabet mit… …   Deutsch Wikipedia

  • Effective results in number theory — For historical reasons and in order to have application to the solution of Diophantine equations, results in number theory have been scrutinised more than in other branches of mathematics to see if their content is effectively computable. Where… …   Wikipedia

  • Prouhet–Thue–Morse constant — In mathematics and its applications, the Prouhet Thue Morse constant is the number au whose binary expansion .01101001100101101001011001101001... is given by the Prouhet Thue Morse sequence. That is,: au = sum {i=0}^{infty} frac{t i}{2^{i+1 =… …   Wikipedia

  • Axel Thue — (* 19. Februar 1863 in Tønsberg, Norwegen; † 7. März 1922 in Oslo) war ein norwegischer Mathematiker, bekannt für seine Beiträge in der Kombinatorik und seine Arbeiten an diophantische Annäherungen. 1914 …   Deutsch Wikipedia

  • List of number theory topics — This is a list of number theory topics, by Wikipedia page. See also List of recreational number theory topics Topics in cryptography Contents 1 Factors 2 Fractions 3 Modular arithmetic …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”