Numărul Thue

Numărul Thue este o caracteristică a unui grafic, o variantă specială a indicelui cromatic . Definit ca numărul minim de culori necesare pentru o colorare care nu se repetă , adică atribuirea de culori la marginile unui grafic astfel încât să nu existe o cale simplă de lungime egală în grafic în care culorile marginilor din prima jumătate ale traseului formează aceeași succesiune ca și culorile marginilor din a doua jumătate a călătoriei.

Introdus în 2002 de un grup de matematicieni condus de Noga Alon [1] , a fost numit după Axel Thue , care a studiat cuvintele fără pătrat necesare pentru a defini riguros un număr.

Variațiile acestei caracteristici au fost, de asemenea, studiate folosind colorarea vârfurilor și, mai general, rutele [2] [3] [4] [5] .

Exemplu

Luați în considerare un pentagon , adică un ciclu cu cinci vârfuri. Dacă colorăm marginile cu două culori, unele dintre cele două margini adiacente vor avea aceeași culoare . Calea formată de aceste două margini va avea o secvență repetată de culori . Dacă colorați marginile cu trei culori, una dintre cele trei culori va fi folosită o singură dată. Calea cu patru margini formată de celelalte două culori fie va avea margini consecutive cu aceeași culoare, fie va forma o secvență care se repetă . Cu patru culori, nu este dificil să evitați repetarea, așa că numărul Thue al ciclului este patru. $X$ $xx$ $xyxy$ $C_{5}$

Rezultate

Alon și colab. au folosit lema locală a lui Lovas pentru a demonstra că numărul Thue al oricărui grafic este cel mult pătratul gradului său maxim. Ei au dat un exemplu care arată că pentru unele grafice este necesară această dependență pătratică. În plus, ei au arătat că numărul Thue al unei căi de patru sau mai multe vârfuri este exact trei, numărul Thue al oricărui ciclu este de cel mult patru și numărul Thue al unui grafic Petersen este exact cinci.

Ciclurile cunoscute cu Thue numărul patru sunt , , ', , , . Alon și colab. au presupus că numărul Thue al oricărui ciclu mai mare este trei. Prin intermediul verificării computaționale, s-au asigurat că ciclurile enumerate mai sus sunt singurele cu Thue numărul patru dintre ciclurile de lungime . În 2002, s-a demonstrat că toate ciclurile de lungime 18 sau mai mare au un număr Thue de 3 [6] . $C_{5}$ $C_{7)$ $C_{9}$ $C_{1}0$ $C_{1}4$ $C_{1}7$ $\leqslant 2001$

Complexitate computațională

Verificarea dacă o colorare are o cale care se repetă este NP-complet , deci verificarea dacă o colorare nu se repetă este conținută în clasa co-NP , iar Fedor Manin a arătat că este co-NP-complet . Problema găsirii unei astfel de colorări aparține ierarhiei polinomiale , iar Manin a demonstrat, de asemenea, că este completă pentru acest nivel. $\Sigma _{2}^{P)$

Note

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

Literatură

Noga Alon , Jaroslaw Grytczuk, Mariusz Haluszczak, Oliver Riordan. Colorări nerepetitive ale graficelor // Structuri aleatorii și algoritmi. - 2002. - T. 21 , nr. 3–4 . — S. 336–346 . doi :/ rsa.10057 .
János Barát, Varjú PP Pe colorarea marginilor fără pătrate ale graficelor // Ars Combinatoria. - 2008. - T. 87 . — S. 377–383 .
Janos Barat, David Wood. Note despre colorarea graficelor nerepetitive // Electronic Journal of Combinatorics. - 2005. - T. 15 , nr. 1 . - arXiv : math.CO/0509608 .
Bostjan Bresar, Sandi Klavzar. Colorarea fără pătrate a graficelor // Ars Combin .. - 2004. - T. 70 . — pp. 3–13 .
James D. Currie. Există cuvinte circulare ternare fără pătrat de lungime n pentru n ≥ 18 // Electronic Journal of Combinatorics. - 2002. - T. 9 , nr. 1 .
Jarosław Grytczuk. Colorări nerepetitive ale graficelor — un sondaj // Jurnalul Internațional de Matematică și Științe Matematice. — 2007.
André Kündgen, Michael J. Pelsmajer. Colorări nerepetitive ale graficelor cu lățime de arbore mărginită // Matematică discretă. - 2008. - T. 308 , nr. 19 . — S. 4473–4478 . - doi : 10.1016/j.disc.2007.08.043 .
Fedor Manin. Complexitatea colorării marginilor nerepetitive ale graficelor. - 2007. - . - arXiv : 0709.4497 .
Marcus Schaefer, Christopher Umans. Completitudine în ierarhia polinomială-timp: un compendiu . - 2005. Arhivat 3 martie 2016.