Nonrepetitive coloring games

Prelegent(ci)

Jarosław Grytczuk

Afiliacja

Uniwersytet Jagielloński

Termin

20 stycznia 2011 12:15

Pokój

p. 5870

Seminarium

Seminarium "Algorytmika"

---

Nonrepetitive coloring games can be played on various combinatorial structures (graphs, words, etc.). Basic idea goes back to Thue, who proved in 1906 that the ntegers can be 3-colored so that any two adjacent segments are not indentical. his striking result has been generalized in many directions, leading to a variety f peculiar coloring problems. Is it true, for instance, that planar graphs can be olored with a bounded number of colors so that any simple path is nonrepetitive?

New aspects appear if a coloring is created by two players, Ann and Ben, say, who tend to minimize and maximize the number of colors used in the play, espectively. In one of possible versions they alternately color consecutive ositive integers in a nonrepetitive way (a new color may be introduced only if ecessary). Using an idea inspired by the algorithmic local lemma one may prove that Ann has a strategy guaranteeing arbitrarily long play if 12 colors are vailable. In the talk I will present some of the recent results, techniques, and open problems of this area.

---