Conjectura Hadwiger (teoria grafurilor)

Conjectura Hadwiger (teoria grafurilor) este una dintre ipotezele nerezolvate ale teoriei grafurilor . Se formulează după cum urmează: fiecare graf cromatic este contractibil cu un graf complet pe vârfuri. $k$ $k$

Altă formulare

Conjectura lui Hadwiger poate fi formulată diferit: în fiecare graf cromatic există neapărat subgrafe conectate care nu se intersectează, astfel încât să existe o muchie între oricare dintre ele. $k$ $k$

Dacă introducem pentru grafic numărul Hadwiger — maximul astfel încât să contractăm graficul complet la vârfuri, atunci ipoteza se formulează ca inegalitatea , unde este numărul cromatic al graficului. $h(G)$ $k$ $G$ $k$ $\chi(G) \leqslant h(G)$ $\chi (G)$

Cazuri speciale

Cazurile și sunt evidente: în primul caz, graficul conține cel puțin o muchie, care este graficul complet ; în al doilea caz, graficul nu este bipartit și conține un ciclu contractabil la . $k=2$ $k = 3$ $K_{2}$ $K_{3}$

Dovada în cauză a fost publicată de însuși Hadwiger în aceeași lucrare în care a fost formulată conjectura. $k = 4$

Din conjectura Hadwiger în cazul rezultă validitatea problemei celor patru culori (demonstrată acum): operația de contracție păstrează planaritatea , iar dacă ar exista un grafic planar 5-cromatic, atunci ar exista o încorporare a graficului în plan. , a cărui inexistenţă rezultă din formula lui Euler . În 1937, Klaus Wagner a demonstrat echivalența problemei patru culori și conjectura Hadwiger pentru , deci acest caz este și el dovedit. $k = 5$ $K_{5}$ $k = 5$

În 1993, N. Robertson, P. Seymour și Robin Thomas au demonstrat conjectura pentru utilizarea problemei celor patru culori. [1] Această dovadă a câștigat Premiul Fulkerson în 1994 . $k = 6$

Căci se știe că, dacă graficul nu satisface ipoteza, atunci este contractibil atât pentru, cât și pentru - grafuri bipartite complete cu părți de cardinalitatea 4 și 4 și, respectiv, cardinalitatea 3 și 5. $k = 7$ $K_{4,4}$ $K_{3,5}$

numărul Hadwiger

Este posibil să se definească o mapare care atribuie un graf maxim , astfel încât să ne contractăm cu graful complet la vârfuri. Găsirea numărului Hadwiger al unui grafic dat este o problemă NP-hard . În orice grafic pentru care există un vârf de grad . [2] Aplicând un algoritm de colorare a graficului lacom , se poate deduce din această afirmație că . $h(G)$ $G$ $k$ $G$ $k$ $G$ $h(G) = k$ $O(k \sqrt{\log k})$ $\chi (G) = O(h(G) \sqrt {\log h(G)})$

Vezi și

Conjectura lui Hadwiger (geometrie combinatorie)

Note

↑ Robertson, Neil; Seymour, Paul; Thomas, Robin (1993), „Conjectura lui Hadwiger pentru grafice fără K6” Arhivat la 10 aprilie 2009 la Wayback Machine
↑ Kostochka, AV (1984), „Liga inferioară a numărului Hadwiger de grafice după gradul mediu”