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

Colorazione totale dei grafi con liste (congettura della)

Congetture  Teoria dei grafi 

Dato un grafo G, si indica con ch”(G) il minimo numero tale che, se per ogni arco vi è una lista di almeno ch”(G) colori tra i quali scegliere, sia possibile colorare i nodi e gli archi di G, in modo tale che:

  • non vi siano due archi dello stesso colore con un estremo in comune,

  • non vi siano due nodi dello stesso colore connessi da un arco;

  • nessun arco abbia un estremo in un nodo dello stesso colore dell’arco.

 

La congettura della colorazione totale dei grafi con liste afferma che ch”(G) = χ”(G), dove χ”(G) è l’indice cromatico totale del grafo ossia il numero di colori necessari per colorare i nodi e gli archi di un grafo G, rispettando le condizioni sopra elencate (v. congettura della colorazione totale dei grafi).

La congettura fu proposta indipendentemente da O.V. Borodin, A.V. Kostochka e D.R. Woodall nel 1997 e da M. Juvan, B. Mohar e R. Škrekovski nel 1998.

 

Nel caso dei grafi planari, ossia disegnabili sul piano senza incroci, vale Δ(G) ≤ χ”(G) ≤ ch”(G) ≤ Δ(G) + 2, dove Δ(G) è il grado massimo del grafo, ossia il massimo numero di archi con un estremo in comune, se:

  • Δ(G) > 8 (Jianfeng Hou, Guizhen Liu e Jianliang Wu, 2007);

  • Δ(G) > 7 e il grafo non contiene due cicli di lunghezza 4 adiacenti; in questo caso ch”(G) = Δ(G) + 1 (Huijuan Wang, Lidong Wu, Xin Zhang, Weili Wu e Bin Liu, 2016);

  • Δ(G) > 7 e il grafo non contiene due cicli di lunghezza 5 adiacenti; in questo caso ch”(G) = Δ(G) + 1 (Huijuan Wang, Bin Liu, Xin Zhang, Lidong Wu, Weili Wu e Hongwei Gao, 2016);

  • Δ(G) > 6 e il grafo non contiene due cicli adiacenti di lunghezza 3 (Bin Liu, Jian Feng Hou e Gui Zhen Liu, 2011);

  • Δ(G) > 6 e il grafo non contiene cicli di lunghezza 5 o 6; in questo caso ch”(G) = Δ(G) + 1 (Bin Liu, Jianfeng Hou e Guizhen Liu, 2008);

  • Δ(G) > 5 e il grafo non contiene cicli di lunghezza 4 o 6; in questo caso ch”(G) = Δ(G) + 1 (Jianfeng Hou, Guizhen Liu e Jiansheng Cai, 2009);

  • Δ(G) > 5 e il grafo non contiene un ciclo di lunghezza 3 adiacente a uno di lunghezza 4; se Δ(G) > 7, ch”(G) = Δ(G) + 1 (Rui Li e Baogang Xu, 2011);

  • Δ(G) > 5 e il grafo non contiene un ciclo di lunghezza 3 adiacente a uno di lunghezza 5; se Δ(G) > 7, ch”(G) = Δ(G) + 1 (Qiuli Lu, Zhengke Miao e Yingqian Wang, 2013);

  • Δ(G) > 4 e il grafo non contiene cicli di lunghezza 3 (Li Zhang e Baoyindureng Wu, 2004);

  • Δ(G) > 4 e il grafo non contiene cicli di lunghezza 4 (Yufa Shen, Guoping Zheng, Wenjie He e Yongqiang Zhao, 2008);

  • Δ(G) > 4 e il grafo non contiene cicli di lunghezza 5 (Weifan Wang e Ko-Wei Lih, 2002).

Contattami

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