Thue-szám

Az 5-kör Thue-száma négy.

A matematika, azon belül a gráfelmélet területén egy gráf Thue-száma az élkromatikus szám Alon et al. (2002) által definiált változata, melyet arról az Axel Thue-ről neveztek el, aki a szám alapjául szolgáló négyzetmentes szavakat tanulmányozta.

Alon et al. úgy definiálják egy gráf nem ismétlődő színezését (nonrepetitive coloring), mint a gráf éleihez színek hozzárendelését oly módon, hogy ne legyen a gráfban olyan páros hosszúságú egyszerű út, melyben az út első felének élszínei ugyanazt a sorozatot alkotják, mint az út második felének élszínei. Egy gráf Thue-száma a nem ismétlődő színezéshez minimálisan szükséges színek száma.

Több szerző is tanulmányozta az elgondolás különböző változatait, melyekben csúcsszínezések vagy általánosabb gráfséták fordulnak elő, köztük Barát and Varjú, Barát and Wood (2005), Brešar and Klavžar (2004), valamint Kündgen and Pelsmajer.

Példa

Tekintsünk egy ötszöget, azaz egy öt csúcsból álló kört. 2-élszínezés után lesz két egymás melletti, azonos x színű él, az ezekből álló út élei pedig az ismétlődő xx szekvenciát alkotják. Ha viszont három színt használunk fel az élek színezésére, a három szín egyikét csak egyszer kell felhasználni; a másik két színt használó maradék négy él vagy ismét tartalmazni fog egymás melletti azonos színeket, vagy a repetitív xyxy élsorozatat. Négy színnel azonban már nem okoz nehézséget az ismétlődések elkerülése. Ezért a C₅ Thue-száma négy.

Eredmények

Alon et al. a Lovász-féle lokális lemma segítségével bizonyítják, hogy bármely gráf Thue-száma legfeljebb a maximális fokszámának négyzetes függvénye; példát is hoznak olyan gráfra, melynél a négyzetes függés ténylegesen megjelenik. Ezen túl megmutatják, hogy egy négy vagy több csúcsból álló út Thue-száma pontosan három, bármely kör Thue-száma legfeljebb négy, a Petersen-gráfé pedig pontosan öt.

A következő körökről ismert, hogy Thue-számuk négy: C₅, C₇, C₉, C₁₀, C₁₄ és C₁₇. Alon et al. sejtése szerint a nagyobb körök Thue-száma három; számítógéppel ellenőrizték, hogy a fenti körökön kívül nincs más négy Thue-számmal rendelkező egészen 2001-es hosszúságig bezárólag. Currie egy 2002-es cikkében megoldotta ezt a kérdést, bebizonyítva, hogy minden, legalább 18 hosszúságú kör Thue-száma 3.

Számítási bonyolultság

Annak vizsgálata, hogy adott színezés tartalmaz-e ismétlődő utat, az NP problémaosztály része, így a színezés nem ismétlődésének tesztelése co-NP, és mint Manin megmutatta, co-NP-teljes. Az ilyen színezés keresésének problémája a polinomhierarchiában $\Sigma _{2}^{P}$, és Marin erre is megmutatta, hogy ezen a hierarchiaszinten teljes.

Fordítás

• Ez a szócikk részben vagy egészben a Thue number című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

Jegyzetek

• (2002) „Nonrepetitive colorings of graphs”. Random Structures & Algorithms 21 (3–4), 336–346. o. DOI:10.1002/rsa.10057.  
• (2008) „On square-free edge colorings of graphs”. Ars Combinatoria 87, 377–383. o. [2016. március 4-i dátummal az eredetiből archiválva]. (Hozzáférés: 2018. április 7.)  
• (2005) „Notes on nonrepetitive graph colouring”. Electronic Journal of Combinatorics 15 (1).  
• (2004) „Square-free coloring of graphs”. Ars Combin. 70, 3–13. o.  
• Currie, James D. (2002). „There are ternary circular square-free words of length n for n ≥ 18”. Electronic Journal of Combinatorics 9 (1).  
• Grytczuk, Jarosław (2007). „Nonrepetitive colorings of graphs—a survey”. International Journal of Mathematics and Mathematical Sciences.  
• (2008) „Nonrepetitive colorings of graphs of bounded tree-width”. Discrete Mathematics 308 (19), 4473–4478. o. DOI:10.1016/j.disc.2007.08.043.  
• Manin, Fedor (2007). „The complexity of nonrepetitive edge coloring of graphs”.  
• (2005) „Completeness in the polynomial-time hierarchy: a compendium”. [2016. március 3-i dátummal az eredetiből archiválva]. (Hozzáférés: 2018. április 7.)