Csütörtöki szám

A Thue szám egy gráf jellemzője, a kromatikus index egy speciális változata . A nem ismétlődő színezéshez szükséges színek minimális száma, azaz színek hozzárendelése a gráf éleihez úgy, hogy a gráfban ne legyen egyszerű páros hosszúságú útvonal, amelyben az élek színei az első felében Az út második felében ugyanazt a sorrendet alkotják, mint az élek színei.

A Noga Alon [1] vezette matematikusok egy csoportja vezette be 2002 -ben, nevét Axel Thue -ról kapta , aki a számok szigorú meghatározásához szükséges négyzet alakú szabad szavakat tanulmányozta.

Ennek a tulajdonságnak a változatait is vizsgálták csúcsszínezéssel, és általánosabban az útvonalakkal [2] [3] [4] [5] .

Példa

Tekintsünk egy ötszöget , azaz egy öt csúcsú ciklust . Ha az éleket két színnel színezzük, akkor a két szomszédos él közül néhány azonos színű lesz . A két él által alkotott útvonalnak ismétlődő színsora lesz . Ha három színnel színezi a széleket, a három szín közül az egyik csak egyszer kerül felhasználásra. A másik két szín által alkotott négyéles útvonalnak vagy ugyanazon színű egymást követő élei lesznek, vagy ismétlődő sorozatot alkotnak . Négy színnel nem nehéz elkerülni az ismétlést, így a ciklus csü-száma négy. $x$ $xx$ $xyxy$ $C_{5}$

Eredmények

Alon és munkatársai Lovas lokális lemmáját használták annak bizonyítására, hogy bármely gráf Thue száma legfeljebb a maximális fok négyzete. Példával mutatták be, hogy egyes gráfoknál ez a másodfokú függés szükséges. Ezenkívül megmutatták, hogy a négy vagy több csúcsból álló útvonal Thue száma pontosan három, bármely ciklus Thue száma legfeljebb négy, és egy Petersen-gráf Thue száma pontosan öt.

Ismert ciklusok Thue négyes számmal: , , ', , , . Alon és munkatársai azt sejtették, hogy bármely nagyobb ciklus Thue száma három. Számítógépes ellenőrzéssel megbizonyosodtak arról, hogy a fent felsorolt ciklusok az egyedüliek, amelyeknek Thue a negyedik a hosszúságú ciklusai között . 2002-ben kimutatták, hogy minden 18 vagy annál hosszabb ciklus Thue-száma 3 [6] . $C_{5}$ ${\displaystyle C_{7))$ $C_{9}$ $C_{1}0$ $C_{1}4$ $C_{1}7$ $\leqslant 2001$

Számítási összetettség

Annak ellenőrzése, hogy egy színezésnek van-e ismétlődő útvonala, NP-teljes , így annak ellenőrzése, hogy egy színezés nem ismétlődő-e, benne van a co-NP osztályban, és Fedor Manin megmutatta, hogy társ-NP-teljes . Az ilyen színezés megtalálásának problémája a polinomiális hierarchiához tartozik , és Manin is bebizonyította, hogy erre a szintre teljes. ${\displaystyle \Sigma _{2}^{P))$

Jegyzetek

↑ Noga, Grischuk, Khalushchiak, Riordan, 2002 .
↑ Barat, Waryu, 2008 .
↑ Barat, Wood, 2005 .
↑ Brechard, Klavzhar, 2004 .
↑ Kündgen, Pelsmeier, 2008 .
↑ Curry, 2002 .

Irodalom

Noga Alon , Jaroslaw Grytczuk, Mariusz Haluszczak, Oliver Riordan. Grafikonok nem ismétlődő színezése // Random Structures & Algorithms. - 2002. - T. 21 , sz. 3–4 . – S. 336–346 . doi :/ rsa.10057 .
Barát János, Varjú PP A gráfok négyzetmentes élszínezéseiről // Ars Combinatoria. - 2008. - T. 87 . – S. 377–383 .
Barát János, David Wood. Megjegyzések a nem ismétlődő gráfszínezéshez // Electronic Journal of Combinatorics. - 2005. - T. 15 , sz. 1 . - arXiv : math.CO/0509608 .
Bostjan Bresar, Sandi Klavzar. Grafikonok négyzet nélküli színezése // Ars Combin .. - 2004. - T. 70 . – 3–13 .
James D. Currie. Vannak háromtagú körkörös négyzet nélküli szavak, amelyek n hosszúságúak , ha n ≥ 18 // Electronic Journal of Combinatorics. - 2002. - T. 9 , szám. 1 .
Jarosław Grytczuk. A grafikonok nem ismétlődő színezése – felmérés // International Journal of Mathematics and Mathematical Sciences. – 2007.
André Kündgen, Michael J. Pelsmajer. Korlátozott faszélességű grafikonok nem ismétlődő színezése // Discrete Mathematics. - 2008. - T. 308 , sz. 19 . — S. 4473–4478 . - doi : 10.1016/j.disc.2007.08.043 .
Fedor Manin. A gráfok nem ismétlődő élszínezésének összetettsége. - 2007. - . - arXiv : 0709.4497 .
Marcus Schaefer, Christopher Umans. Teljesség a polinom-idő hierarchiában: kompendium . - 2005. Archiválva : 2016. március 3.