Don't take life too seriously: it's just a temporary situation

Hadwiger (congettura di) (I)

Congetture  Teoria dei grafi 

La congettura proposta da Hugo Hadwiger nel 1943 afferma che se servono n colori per colorare i nodi di un grafo, in modo che non vi siano due nodi dello stesso colore collegati da un arco, il grafo può essere decomposto in modo che contenga n sottografi, ciascuno connesso a tutti gli altri.

In altri termini, facendo collassare tra loro alcuni nodi collegati mantenendo gli archi (più tecnicamente, riducendo il grafo a un suo minore), si può fare in modo che il grafo risultante contenga un grafo completo a n nodi.

Per esempio, sono necessari 4 colori per colorare il grafo della figura seguente, che pure non contiene un sottografo equivalente al grafo completo a 4 nodi.

 

Esempio di grafo che rochiede 4 colori

 

Facendo collassare i nodi riuniti nei rettangoli con sfondo grigio, in nodi che risultano collegati tra loro dagli archi in blu, il grafo risultante contiene un sottografo completo con 4 nodi, formato dai nodi collassati.

 

La congettura è strettamente connessa al teorema dei 4 colori (v. numeri di Heawood) e nel caso delle mappe planari afferma che data una mappa che richieda 4 colori per essere colorata in modo che regioni adiacenti non siano dello stesso colore, si possono far collassare regioni adiacenti, fino a ridurla a 4 regioni, ciascuna delle quali confinante con tutte le altre.

 

Il caso n = 2 è banale: se un grafo richiede due colori, contiene almeno 2 nodi collegati da un arco, quindi un sottografo completo a 2 nodi.

Anche il caso n = 3 è facile: un grafo che richiede 3 colori non è bipartito e un grafo non bipartito contiene un ciclo di lunghezza dispari, che può essere contratto a un ciclo di lunghezza 3, ossia a un grafo completo a 3 nodi.

Hugo Hadwiger (Karlsruhe, Germania, 23/12/1908 – Berna, Svizzera, 29/10/1981) risolse il caso n = 4 nello stesso articolo nel quale propose la congettura (1943).

Il caso n = 5 implica il teorema dei 4 colori e già nel 1937 Klaus Wagner aveva dimostrato che è equivalente a esso; dal 1976, quando Kenneth Appel e Wolfgang Hachen dimostrarono il teorema, sappiamo che la congettura in questo caso vale.

Il caso n = 6 fu dimostrato vero nel 1993 da Neil Robertson, Paul Seymour e Robin Thomas, con un lavoro che valse loro il premio Fulkerson.

Per n = 7 Ken-ichi Kawarabayashi dimostrò che il collasso dei nodi porta o a un grafo completo a 7 nodi o a un grafo K3, 5 e Toft e lo stesso Kawarabayashi dimostrarono nel 2005 che il collasso dei nodi porta o a un grafo completo a 7 nodi o a un grafo K4, 4, quindi l’operazione deve portare o al grafo completo o sia a un grafo K3, 5, sia a un grafo K4, 4 (eseguendo l’operazione in modi diversi). Un grafo Km, n è un grafo i cui nodi sono diviso in due sottoinsiemi di m e n nodi, con ogni nodo di un sottoinsieme connesso a tutti quelli dell’altro.

 

Ken-ichi Kawarabayashi e Bruce Reed dimostrarono nel 2009 che il minimo controesempio alla congettura di Hawiger, se esiste, ha al massimo Limite superiore per il numero di nodi del minimo controesempio nodi, dove Formula per al definizione di p. Il numero è talmente spaventoso, anche per n = 7, che per ora non esiste alcuna speranza di poter dimostrare il teorema esaminando tutti i grafi fino a quel numero di nodi. Il miglior algoritmo noto per determinare il massimo grafo completo ottenibile collassando i nodi di un grafo, dovuto agli stessi ricercatori, richiede un numero di passi che aumenta col quadrato del numero di nodi.

 

Grazie a Dominic Van der Zypen sappiamo dal 2012 che la congettura non vale per grafi che richiedono un’infinità numerabile di colori. Come spesso accade, con l’infinito che la caviamo in fretta, il finito può richiedere più tempo.

 

Tra le varianti sul tema, segnalo che Neil Robertson, Sanders, Paul Seymour, e Robin Thomas dimostrarono nel 2001 che un grafo cubico (nel quale ogni nodo è connesso a esattamente altri 3) che richieda 4 colori può essere ridotto, facendo collassare i nodi, al grafo di Petersen mostrato nella figura seguente, come aveva supposto W.T. Tutte.

 

Grafo di Petersen

 

 

Il matematico ungherese György Hajós propose una versione più forte della congettura di Hadwiger, che fu però dimostrata false per n > 6 (v. congettura di Hajós).

Contattami

Potete contattarmi al seguente indirizzo bitman[at]bitman.name per suggerimenti o segnalazioni d'errori relativi a questo articolo.