Thue číslo

Číslo Thue  je charakteristikou grafu, speciální varianty chromatického indexu . Definováno jako minimální počet barev požadovaný pro neopakující se vybarvování , to znamená přiřazování barev okrajům grafu tak, že v grafu neexistuje jednoduchá cesta sudé délky, ve které jsou barvy okrajů v první polovině cesty tvoří stejnou sekvenci jako barvy okrajů v druhé polovině cesty.

Zavedena v roce 2002 skupinou matematiků vedenou Nogou Alonem [1] , byla pojmenována po Axelu Thueovi , který studoval čtvercová volná slova potřebná k důsledné definici čísla.

Variace tohoto rysu byly také studovány pomocí barvení vrcholů a obecněji tras [2] [3] [4] [5] .

Příklad

Uvažujme pětiúhelník , tedy cyklus s pěti vrcholy. Pokud obarvíme okraje dvěma barvami, některé ze dvou sousedních hran budou mít stejnou barvu . Cesta tvořená těmito dvěma hranami bude mít opakující se sekvenci barev . Pokud obarvíte okraje třemi barvami, jedna ze tří barev bude použita pouze jednou. Čtyřhranná cesta tvořená dalšími dvěma barvami bude mít buď po sobě jdoucí hrany se stejnou barvou, nebo bude tvořit opakující se sekvenci . Se čtyřmi barvami není těžké vyhnout se opakování, takže číslo Thue cyklu je čtyři.

Výsledky

Alon et al . Uvedli příklad ukazující, že pro některé grafy je tato kvadratická závislost nezbytná. Navíc ukázali, že Thue číslo cesty čtyř nebo více vrcholů je právě tři, Thue číslo libovolného cyklu je maximálně čtyři a Thue číslo Petersenova grafu je přesně pět.

Známé cykly se čtvrtým číslem čtyři jsou , , ', , , . Alon et al předpokládali, že číslo Thue jakéhokoli většího cyklu je tři. Pomocí výpočetní verifikace se ujistili, že výše uvedené cykly jsou jediné, které mají mezi cykly délky čt čtyři . V roce 2002 se ukázalo, že všechny cykly o délce 18 a více mají Thue číslo 3 [6] .

Výpočetní složitost

Kontrola, zda zbarvení má opakující se cestu, je NP-úplné , takže kontrola, zda se zbarvení neopakuje, je obsaženo ve třídě co-NP a Fedor Manin ukázal, že je ko-NP-úplné . Problém najít takové zbarvení patří do polynomiální hierarchie a Manin také dokázal, že je pro tuto úroveň kompletní.

Poznámky

  1. ↑ Noga, Grischuk, Khalushchiak, Riordan, 2002 .
  2. ↑ Barat, Waryu, 2008 .
  3. ↑ Barat, Wood, 2005 .
  4. ↑ Brechard, Klavzhar, 2004 .
  5. ↑ Kündgen, Pelsmeier, 2008 .
  6. ↑ Curry, 2002 .

Literatura