Tout graphe planaire sans cycle de longueurs est acycliquement liste coloriable

Hervé Hocquard

Description

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

Sujets

• University of Bordeaux
• maths

Informations

• Publié par: pefav
• Nombre de lectures: 61
• Langue: Français

Extrait

oHqcreév 3/ H 31 Montkaë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/2 reH 3 ,MrdkaicHovéuacq

k-liste coloration acyclique Si pour toute assignation de listesLsatisfaisant∀v∈V(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ésultats Dénitions Annexe Quelques résultats

phesegraaireplancanoitardeuqilcyasntMoëlloCoersi

rCiesstaioatoroliM,drauqnoMlëakclanahesp

Col oration acyclique par listes ns Ré A s n u n lt e a x ts e Q D u é e  lq ni u ti e o s 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.

ireslcqianycrgpaeued 3/33 Hervé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.