Mychelskian

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 10 noiembrie 2021; verificarea necesită 1 editare .

Un grafic Mycielskian sau Mycielski al unui graf nedirecționat este un grafic creat prin aplicarea construcției Mycielski ( Mycielski 1955 ). Designul păstrează absența triunghiurilor , dar crește numărul cromatic . Mycelsky a arătat că repetând construcția în mod repetat la graficul inițial fără triunghi, se pot obține grafice fără triunghi de dimensiuni arbitrar mari.

Constructii

Fie n vârfuri ale graficului dat G v 0 , v 1 și așa mai departe. Graficul Mycielski μ( G ) al lui G conține G ca subgraf și încă n +1 vârfuri — câte un vârf u i pentru fiecare vârf v i al lui G și încă un vârf w . Fiecare vârf u i este legat printr-o muchie de w astfel încât vârfurile să formeze o stea K 1, n . În plus, pentru fiecare muchie v i v j a graficului G , graficul Mycielski include două muchii — u i v j și v i u j .

Astfel, dacă G are n vârfuri și m muchii, μ( G ) are 2 n + 1 vârfuri și 3 m + n muchii.

Exemplu

Ilustrația prezintă construcțiile lui Mycielski aplicate unui ciclu cu cinci vârfuri - v i pentru 0 ≤ i ≤ 4. Mycielskianul rezultat este graficul Grötsch , un grafic cu 11 vârfuri și 20 de muchii. Graficul Gröcz este cel mai mic grafic fără triunghi cu număr cromatic 4 ( Chvátal 1974 ).

Repetarea multiplă a construcției mychelskiene

Aplicând în mod repetat construcția Mycelskianului, începând cu un grafic cu o singură muchie, obținem o succesiune de grafice M i = μ( M i -1 ), numite uneori și grafice Mycelsky. Primele grafice din această secvență sunt graficele M 2 = K 2 cu două vârfuri conectate printr-o muchie, ciclul M 3 = C 5 și graficul Grötzsch cu 11 vârfuri și 20 de muchii.

În general, graficele M i din succesiune nu au triunghiuri , ( i -1) -conectate cu vârfuri și i - cromatice . M i are 3 × 2 i -2 - 1 vârfuri (secvența A083329 în OEIS ). Numărul de muchii din M i pentru i mic este

0, 0, 1, 5, 20, 71, 236, 755, 2360, 7271, 22196, 67355, ... (secvența A122695 în OEIS ).

Proprietăți

Dacă G are număr cromatic k , atunci μ( G ) are număr cromatic k + 1 ( Mycielski 1955 ).
Dacă G nu are triunghiuri , atunci μ( G ) nu are nici triunghiuri ( Mycielski 1955 ).
Mai general, dacă G are un număr de clică ω( G ), atunci μ( G ) are un număr de clică max(2,ω( G )) ( Mycielski 1955 ).
Dacă G este un grafic coeficient critic , atunci este și μ( G ) ( Došlić 2005 ). În special, fiecare grafic M i pentru i ≥ 2 este factor critic.
Dacă G este un ciclu hamiltonian , atunci este și μ( G ) ( Fisher, McKenna, Boyer 1998 ).
Dacă G are un număr dominant γ( G ), atunci μ( G ) are un număr dominant γ( G )+1 ( Fisher, McKenna, Boyer 1998 ).

Con peste grafice

O generalizare a lui Mychelskian numită con peste un grafic a fost introdusă de Stiebitz ( Stiebitz 1985 ) și ulterior studiată de Tardif ( Tardif 2001 ) și Lin, Wu, Lam și Gu ( Lin, Wu, Lam, Gu 2006 ).

Fie G un grafic cu o mulțime de vârfuri și o mulțime de muchii . Fie dat un număr întreg . Pentru un graf G , numim un m-mychelskian un graf cu un set de vârfuri ${\displaystyle V^{0}=\left\{v_{1}^{0},v_{2}^{0},...,v_{n}^{0}\right\))$ $E^{0}$ $m\geq 1$ $\mu _{m}(G)$

V^{0}\cup V^{1}\cup V^{2}\cup ...\cup V^{m}\cup \left\{u\right\)

unde este copia i-a pentru , și setul de muchii $V^{i}=\left\{v_{j}^{i}:v_{j}^{0}\in V^{0}\right\}$ $V^{0}$ $i=1,2,...,m$

E^{0}\cup \left(\bigcup _{i=0}^{m-1}\left\{v_{j}^{i}v_{j'}^{i+1} :v_{j}^{0}v_{j'}^{0}\în E^{0}\right\}\right)\cup \left\{v_{j}^{m}u:v_{ j}^{m}V^{m}\right\}

Definiți ca un grafic obținut prin adăugarea unui vârf universal u. Evident, mychelskian este doar [1] . $\mu _{0}(G)$ $\mu _{1}(G)$

Note

↑ Lin, Wu, Lam, Gu, 2006 .

Literatură

Vaclav Chvatal. Grafice și combinatorie (Proc. Capital Conf., George Washington Univ., Washington, DC, 1973). - Springer-Verlag, 1974. - T. 406. - S. 243-246. — (Note de curs la matematică).
Tomislav Došlić. Mycielskians și potriviri // Discuții Mathematicae Graph Theory. - 2005. - T. 25 , nr. 3 .
David C. Fisher, Patricia A. McKenna, Elizabeth D. Boyer. Hamiltonicitatea, diametrul, dominația, împachetarea și partițiile biclique ale graficelor lui Mycielski // Matematică aplicată discretă. - 1998. - T. 84 , nr. 1-3 . - S. 93-105 . - doi : 10.1016/S0166-218X(97)00126-1 .
Wensong Lin, Jianzhuan Wu, Peter Che Bor Lam, Guohua Gu. Câțiva parametri ai micielskienilor generalizați // Matematică aplicată discretă. - 2006. - T. 154 , nr. 8 . - S. 1173-1182 . - doi : 10.1016/j.dam.2005.11.001 .
Jan Mycielski. Sur le coloriage des graphes // Colloq. Matematică.. - 1955. - T. 3 . - S. 161-162 .
M. Stiebitz. Beiträge zur Theorie der färbungskritschen Graphen. — Teză de abilitare, Technische Universität Ilmenau , 1985. După cum este citat în Tardif ( 2001 ).
C. Tardif. Numerele cromatice fracționale ale conurilor peste grafice // Journal of Graph Theory. - 2001. - T. 38 , nr. 2 . - S. 87-94 . - doi : 10.1002/jgt.1025 .
Weisstein, Eric W. Mycielski Graph (engleză) pe site-ul web Wolfram MathWorld .