Pagina Radice del Progetto: List Coloring di grafi bipartiti

Dato un grafo bipartito G=(V,E), di grado massimo $\Delta$, si assuma che ad ogni arco risulti associata una palette di almeno $\Delta$ colori. Fred Galvin ha dimostrato che è sempre possibile assegnare ad ogni arco un colore preso dalla rispettiva palette, in modo che ogni due archi con un estremo in comune abbiano colore diverso. Vorremmo codificare il suo algoritmo.

Come riferimento, consiglio:

Slivnik, Tomawz
Short proof of Galvin's theorem on the list-chromatic index of a bipartite multigraph.
Combin. Probab. Comput. 5 (1996), no. 1, 91--94.

Sarà comunque bene procurarsi il lavoro originale.

Galvin, Fred
The list chromatic index of a bipartite multigraph.
J. Combin. Theory Ser. B 63 (1995), no. 1, 153--158.

nota: l'algoritmo non richiede di per sè un pesante sforzo implementativo, però richiede una subroutine per l'edge-coloring di grafo bipartito. (Non dovrebbe essere un problema trovare tale subroutine in web, nell'attesa che venga sviluppata dai compagni impegnati nell'apposito progetto). Inoltre varrebbe la pena prevedere la possibilità di far visualizzare i passi dell'algoritmo attraverso l'utilizzo di un qualche tool di visualizzazione.

created: 25 Aprile 2001
updated: 25 Aprile 2001