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

Colorazione totale dei grafi (congettura della)

Congetture  Teoria dei grafi 

Vi sono vari modi di colorare un grafo, ciascuno dei quali richiede un differente numero minimo di colori.

 

Il numero di colori necessari per colorare i nodi di un grafo G, in modo tale che non vi siano due nodi dello stesso colore connessi da un arco, è detto “numero cromatico” del grafo e indicato con χ(G) (v. anche costanti di Tutte – Beraha).

Il numero di colori necessari per colorare gli archi di un grafo G, in modo tale che non vi siano due archi dello stesso colore con un estremo in comune, è detto “indice cromatico” del grafo e indicato con χ’(G).

Il numero di colori necessari per colorare i nodi e gli archi di un grafo G, in modo tale che non vi siano due nodi dello stesso colore connessi da un arco, due archi dello stesso colore con un estremo in comune né archi connessi a nodi dello stesso colore dell’arco, è detto “indice cromatico totale” del grafo e indicato con χ”(G).

 

La figura seguente mostra un esempio dei tre numeri di colorazioni sullo stesso grafo: la colorazione a sinistra mostra che in questo caso χ(G) = 2, quella centrale che χ’(G) = 3 e quella di destra che χ”(G) = 5.

 

Esempi di colorazioni di un grafo

 

 

La congettura della colorazione totale dei grafi, proposta indipendentemente da Mehdi Behzad e Vadim Georgievich Vizing (Kiev, 25/3/1937 – 23/8/2017) tra il 1964 e il 1968, afferma che χ”(G) ≤ Δ(G) + 2, dove Δ(G) è il grado massimo del grafo, ossia il massimo numero di archi con un estremo in comune.

Si dimostra facilmente che χ”(G) ≥ Δ(G) + 1 e si conoscono grafi (in particolare i cicli con lunghezza non multipla di 3 e i grafi bipartiti completi Kn, n), tali che χ”(G) = Δ(G) + 2, ma nessuno con χ”(G) > Δ(G) + 2.

I migliori risultati noti sono:

  • χ”(G) ≤ Δ(G) + 1026 (Michael Molloy e Bruce Reed, 1998);

  • χ”(G) ≤ Δ(G) + 8log8Δ(G) (Hugh Hind, Michael Molloy e Bruce Reed 1998);

  • χ”(G) ≤ ch’(G) + 2, dove ch’(G) è il minimo numero tale che sia possibile colorare gli archi di un grafo G, in modo tale che non vi siano due archi dello stesso colore con un estremo in comune, se per ogni arco vi è una lista di almeno ch’(G) colori tra i quali scegliere (v. congettura di Diniz).

 

Nel 1996 H.P. Yap dimostrò che:

  • per i grafi completi χ”(Kn) = n + 1 = Δ(G) + 2, se n è pari, e χ”(Kn) = n = Δ(G) + 1, se n è dispari;

  • per i grafi bipartiti completi; χ”(Km, n) = Δ(G) + 2, se m = n, e χ”(m, n) = Δ(G) + 1, se mn;

  • per i cicli χ”(Cn) = Δ(G) + 1, se n multiplo di 3, e χ”(Cn) = n = Δ(G) + 2, se n non è multiplo di 3.

 

La congettura è stata dimostrata per alcune categorie di grafi:

  • per i grafi con Δ(G) ≤ 3 (M. Rosenfeld, 1971);

  • per i grafi con Δ(G) = 4 (A.V. Kostochka, 1977);

  • per i grafi con Δ(G) = 5 (A.V. Kostochka, 1996);

  • per i grafi planari con Δ(G) > 7 (O.V. Borodin, 1989);

  • per i grafi planari con Δ(G) ≤ 7 (Daniel P. Sanders e Vue Zhao, 1999).

  • per i grafi planari con Δ(G) = 6, senza triangoli adiacenti (Xiang-Yong Sun, Jian-Liang Wu, Yu-Wen Wu e Jian-Feng Hou, 2009);

  • per i grafi disegnabili con un solo incrocio con Δ(G) ≥ 16 (X. Zhang, J. Wu e G. Liu, 2012);

  • per i grafi disegnabili con un solo incrocio con χ(G) ≤ 4 e Δ(G) ≥ 10 o Δ(G) ≥ 8, ma senza due triangoli adiacenti (J. Czap2013).

 

Dalla congettura, tuttora non dimostrata, che ch’(G) = χ’(G) seguirebbe che χ”(G) ≤ Δ(G) + 3 (v. congettura di Diniz).

 

In seguito venne proposta una versione più forte della congettura per i grafi planari (ossia disegnabili sul piano senza incroci), vale a dire che per questi grafi χ”(Cn) = Δ(G) + 1, per Δ(G) > 3. Su questa versione sono stati fatti notevoli progressi:

  • nel 1987 O.V. Borodin dimostrò che vale se Δ(G) ≥ 16;

  • nel 1989 lo stesso matematico ridusse il limite a 14;

  • nel 1997 sempre Borodin ridusse il limite a 12;

  • nel 1997 O.V. Borodin, A.V. Kostochka e D.R. Woodall lo ridussero a 11;

  • nel 2007 Weifan Wang lo ridusse a 10;

  • nel 2008 Ɓukasz Kowalik, Jean-Sébastien Sereni e Riste Škrekovski lo ridussero a 9;

  • nel 2009 Lan Shen e Yingqian Wang dimostrarono che vale per grafi con Δ(G) = 7, privi di cicli di lunghezza 5;

  • nel 2009 X.Y. Sun, J.L. Wu, Y.W. Wu e J. F. Hou dimostrarono che vale per grafi senza triangoli adiacenti e privi di cicli di lunghezza maggiore di 4;

  • nel 2010 J. Zhang e Y. Wang dimostrarono che vale per grafi con Δ(G) ≥ 6, senza cicli adiacenti di lunghezza 3 o 4;

  • nel 2011 J. Hou, B. Liu, G. Liu e J. Wu dimostrarono che vale per grafi co Δ(G) ≥ 5 e privi di cicli di lunghezza 4 e 6 e per grafi con Δ(G) ≥ 6 e privi di cicli di lunghezza 5 e 6;

  • nel 2012 H.J. Wang e J.L. Wu dimostrarono che vale per grafi con Δ(G) ≥ 7 e senza cicli di lunghezza 4 adiacenti.

I grafi K2, C5 e K4, planari, mostrano che la congettura non vale per Δ(G) = 1, 2 e 3, quindi gli unici casi irrisolti sono quelli con 3 < Δ(G) < 9.

 

Nel 1989 Abdón Sánchez-Arroyo dimostrò che determinare se χ”(Cn) = Δ(G) + 1 è un problema NP-completo.

Contattami

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