Cet ouvrage fait partie de la bibliothèque YouScribe
Obtenez un accès à la bibliothèque pour le lire en ligne
En savoir plus

Tout graphe planaire sans cycle de longueurs est acycliquement liste coloriable

De
35 pages
Coloration acyclique par listes Résultats Annexe Tout graphe planaire sans cycle de longueurs 4 à 12 est acycliquement 3-liste coloriable Hervé Hocquard Mickaël Montassier Université Bordeaux 1, France JGA 2009 6 Novembre 2009 1/33 Hervé Hocquard, Mickaël Montassier Coloration acyclique de graphes planaires

  • planaire sans cycle de longueurs

  • coloration acyclique de graphes planaires

  • approche eléments de preuve bilan des charges conclusion


Voir plus Voir moins
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.
Un pour Un
Permettre à tous d'accéder à la lecture
Pour chaque accès à la bibliothèque, YouScribe donne un accès à une personne dans le besoin