7 jours d'essai offerts
Cet ouvrage et des milliers d'autres sont disponibles en abonnement pour 8,99€/mois
oHqcreév3/H31Montkaël,MicuardnoitaroloCreissaphraegedquliycac
JGA 2009 6 Novembre 2009
plesaiansre
Hervé Hocquard Mickaël Montassier
Université Bordeaux 1, France
Coloration acyclique par listes Résultats Annexe
Tout graphe planaire sans cycle de longueurs 4 à 12 est acycliquement 3-liste coloriable
3/2reH3,MrdkaicHovéuacq
k-liste coloration acyclique Si pour toute assignation de listesLsatisfaisantvV(G), |L(v)| ≥k, le grapheGadmet uneL-coloration acyclique, alorsGest dit coloriableacycliquement k -liste.
s
L-coloration acyclique par listes Un grapheGestacycliquement L-coloriablesi pour l'assignation de listes de couleurs aux sommets deG, il existe une coloration acycliquecdes sommets deGtelle que c(v)L(v)pour toutvdeV(G).
Coloration acyclique par listes RésultatsDénitions AnnexeQuelques résultats
phesegraaireplancanoitardeuqilcyasntMoëlloCoersi
rCiesstaioatoroliM,drauqnoMlëakclanahesp
Col oration acyclique par listesns RéAsnunlteaxtseQDuéelqniutieos résultats
Théorème[Borodin, Fon-Der Flaas, Kostochka, Raspaud, Sopena '02] Tout graphe planaire est acycliquement 7-liste coloriable.
Conjecture[Borodin, Fon-Der Flaas, Kostochka, Raspaud, Sopena '02] Tout graphe planaire est acycliquement 5-liste coloriable.
ireslcqianycrgpaeued3/33HervéHoc
O.V. Borodin, D.G. Fon-Der Flaass, A.V. Kostochka, A. Raspaud and É. Sopena Acyclic list 7-coloring of planar graphs. J. Graph Theory, 40(2) :83-90, 2002.