2007/01/01 by Jarosław Grytczuk · 53 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Limits and Structures in Graph Theory #Complexity and Algorithms in Graphs #Algorithm #Computer science
paper · pdf · doi:10.1155/2007/74639
published in International Journal of Mathematics and Mathematical Sciences 2007, 1-10 (Hindawi Publishing Corporation)
openalex publication_date 2007/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/23
A vertex coloring<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" id="E1"><mml:mi>f</mml:mi></mml:math>of a graph<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" id="E2"><mml:mi>G</mml:mi></mml:math>is nonrepetitive if there are no integer<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" id="E3"><mml:mrow><mml:mi>r</mml:mi><mml:mo>≥</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:math>and a simple path<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" id="E4"><mml:mrow><mml:msub><mml:mi>v</mml:mi><mml:mn>1</mml:mn></mml:msub><mml:mo>,</mml:mo><mml:mo>…</mml:mo><mml:mo>,</mml:mo><mml:msub><mml:mi>v</mml:mi><mml:mrow><mml:mn>2</mml:mn><mml:mi>r</mml:mi></mml:mrow></mml:msub></mml:mrow></mml:math>in<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" id="E5"><mml:mi>G</mml:mi></mml:math>such that<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" id="E6"><mml:mrow><mml:mi>f</mml:mi><mml:mrow><mml:mo>(</mml:mo><mml:mrow><mml:msub><mml:mi>v</mml:mi><mml:mi>i</mml:mi></mml:msub></mml:mrow><mml:mo>)</mml:mo></mml:mrow><mml:mo>=</mml:mo><mml:mi>f</mml:mi><mml:mrow><mml:mo>(</mml:mo><mml:mrow><mml:msub><mml:mi>v</mml:mi><mml:mrow><mml:mi>r</mml:mi><mml:mo>+</mml:mo><mml:mi>i</mml:mi></mml:mrow></mml:msub></mml:mrow><mml:mo>)</mml:mo></mml:mrow></mml:mrow></mml:math>for all<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" id="E7"><mml:mrow><mml:mi>i</mml:mi><mml:mo>=</mml:mo><mml:mn>1</mml:mn><mml:mo>,</mml:mo><mml:mo>…</mml:mo><mml:mo>,</mml:mo><mml:mi>r</mml:mi></mml:mrow></mml:math>. This notion is a graph-theoretic variant of nonrepetitive sequences of Thue. The paper surveys problems and results on this topic.