Type: Article
Publication Date: 2007-01-01
Citations: 58
DOI: https://doi.org/10.1155/2007/74639
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.