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

Colorazione degli archi con liste (congettura della)

Congetture  Teoria dei grafi 

Dato un grafo G, si indica con ch’(G) il minimo numero tale che sia possibile colorare gli archi di 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.

La congettura della colorazione degli archi con liste, proposta nel 1985 da B. Bollabas e A.J. Harris, afferma che ch’(G) = χ’(G). Su di essa si sa che:

  • ch’(G) < 2χ’(G), dove χ’(G) è l’indice cromatico del grafo ossia 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;

  • asintoticamente ch'(G) / χ(G) tende a 1 (Jeff Kahn, 2000);

  • è vero il caso speciale dei grafi bipartiti completi, noto come “congettura di Diniz”.

 

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

  • Δ(G) > 8 (O.V. Borodin, 1990);

  • Δ(G) = 8 (J.A. Bondy e U.S. R. Murty, 2008);

  • Δ(G) > 7 e il grafo non contiene un ciclo di lunghezza 3 adiacente a uno di lunghezza 4; in questo caso χ’(G) = ch’(G) = Δ(G) (Rui Li e Baogang Xu, 2011);

  • Δ(G) > 7 e il grafo non contiene un ciclo di lunghezza 3 adiacente a uno di lunghezza 5; in questo caso χ’(G) = ch’(G) = Δ(G) (Qiuli Lu, Zhengke Miao e Yingqian Wang, 2013);

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

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

  • Δ(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.