Tout graphe planaire sans cycle de longueurs est acycliquement liste coloriable

HERVE HOCQUARD - pefav

Français

35 pages

Démarrez votre essai gratuit

Lire un extrait

Obtenez un accès à la bibliothèque pour le consulter en ligne
En savoir plus

A propos
Informations

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

Documents

Education

Cours

University of Bordeaux

maths

Informations

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

Du même publieur

Voir tout

Chapitre2 les matrices

Cours mathématique

James Bond

Digital mathematics libraries: The good the bad the ugly

THIERRY BOUCHE

CHAP CROISSANCE CAPITAL ET PROGRÈS TECHNIQUE

STEPHEN POLOZ

TITE LIVE Histoire Romaine V V V

MARCUS PAPIRIUS

Chapitre Le disque et le cylindre de révolution I LE DISQUE

Signaler un problème

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 listesLsatisfaisant∀v∈V(G), |L(v)| ≥k, le grapheGadmet uneL-coloration acyclique, alorsGest dit coloriableacycliquement k -liste.

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.

YouScribe

Le catalogue

Le service

Les conditions

Rapport de stage conclusion Poésie en prose Livre en ligne Tout le catalogue Toute la communauté