Chapitre 4 Coloration de graphes

Le nombre chromatique est le plus petit nombre ce couleurs nécessaires à son coloriage 3 Propriétés Si le graphe G admet un sous graphe complet d'odre 3 ou 4 alors le nombre chromatique est supérieur ou égal à 3 ou 4 donc si m est l'ordre le plus grand des sous graphes complets du graphe G, alors le nombre chromatique de G

VI Coloration de graphe - math-baudon

Le nombre chromatique d’un graphe est le plus petit nombre de couleurs permettant de colorier ce graphe Remarque importante: Si un graphe est complet, son nombre chromatique est égal à son ordre En effet, chaque sommet est adjacent à tous les autres Il faut donc une couleur différente pour chaque sommet, et bien entendu, cela suffit

Chapitre 4 Coloration de graphes

Le nombre a-chromatique d’un graphe G not´eΨ(G) est le nombre maximum de cou-leurs pour lequel G poss`ede une a-coloration Par exemple dans un graphe biparti complet moins un couplage parfait K" n,n, le nombre a-chromatique est n c’est-`a-dire la taille de la bipartition (voir la ﬁgure 4 2 pour visualiser la a-coloration ayant un

L3: cours Graphes I6S3 Chapitre III : coloration de graphe

L3: cours Graphes I6S3 Chapitre III : coloration de graphe D e nitions et propri et es Nombre chromatique D e nition Le nombre chromatique ˜(G) d’un graphe G est le plus petit entier k tel que G soit k-coloriable Si ˜(G) = k, G est dit k-chromatique 8 de 48

TD n 5 : Coloration de graphes

TD no5 : Coloration de graphes Exercice 1 – Exemples introductifs a) Quel est le nombre chromatique de la chaine a n sommets P n? b) Quel est le nombre chromatique du graphe complet K n? c) Quel est le nombre chromatique du cycle C n? Exercice 2 – Graphes bipartis a) Rappeler ce qu’est un graphe biparti Donner un exemple

Coloration de graphes: algorithmes et structures

Cliques et coloration D e nition Une clique est un ensemble de sommets du graphe deux a deux reli es On notera la taille d’une clique maximale et ˜le nombre minimum de couleurs requises pour colorer le graphe G Remarque ˜ R eciproque? Il existe des graphes sans triangle dont le nombre chromatique est arbitrairement grand

1 VOCABULAIRE DE BASE a Graphe

La coloration d’un graphe est toujours possible En effet, si (G) est un graphe d’ordre n, on peut toujours le colorer en utilisant n couleurs distinctes b Nombre chromatique Définition: Le nombre chromatique d’un graphe est le plus petit nombre de couleurs permettant de le colorer Exemple: « Poissons » Sommet Couleur Remarque A (1

Coloration d’un graphe - info-llgfr

Question 5 Écrire en Caml une fonction coloration prenant en argument un graphe G et renvoyant le tableau des couleurs attribuées aux sommets de G par l’algorithme décrit ci-dessus coloration:graphe >intvect Partie III Déﬁnition du nombre chromatique de G Soit G un graphe et p un entier strictement positif

LE NOMBRE MAXIMAL DE COLORATIONS DUN GRAPHE HAMILTONIEN

On voit que le nombre maximal des 3-colorations d'un graphe hamiltonien est atteint dans la classe des graphes hamiltoniens G :~ n sommets, de nombre chromatique 3'(G)= 3, qui ont un nombre minimal d'ar&es, compte tenu de la caract6risation suivante: Th6or~me 2

Chapitre4

Colorationdegraphes

Dansce chapitre,nousdiscutonsdes di

´erentescolorationsdegraphesetdesprobl` emes

decomplexit ´eassoci´es.Nousnousfocalisonsessen tiellementsurlab-colorationetlaf- coloration,et auxnombreschromatiques associ´ es. Lapremi` eresectioncorrespond`aune introductionauxprobl` emesdecoloration,en rappelantcequiestconn usur lescolorationsclassiques .Nouspr´esen tonsdansladeuxi`eme sectionlaa-colorationetleth ´eor` emed'interp olationassoci´e.Nouspr´esentonsalorsdansla troisi`emesectionlab-coloration,etquelquesr ´esultatssur lastructuredesb-spectres.Dans laquatri` emesection,nouspr´esentons laf-colorationetuncertainnom breder ´esultats n´egatifs. Jepr´ esenteautraversdecesdiscussionsquelquesr ´esultats personnels,essentiellement `aproposdela b-colorationetdelaf-coloration.Nousavons ainsiprouv´ ed'unepartque pourtoutensemble d'entiers, ilexisteungraphedeb-spectreouf-spectreassoci´e.Nous avonsd'autrepartcaract´eris ´ela complexit´ edesprobl`emesded´ecisionet d'approxima- tionasso ci´es,enprouvantparexemplelanon-approximabilit´e desnombre schromatiques correspondants. Lestrav auxpr´esent´es danscechapitreont´et´eobtenusencollaborationavecl' ´etudian t enth` eseTaoufikFaik.

4.1Introductio n

Desapplicationsc ommel'ordonnancement detˆaches,l'allocation defr´e quences,l'al-

locationsderegistres,der ´epartition deservic esdansles r´eseauxpeuventˆetremo d´elis ´ees

commeunprobl `emede colorationdegraphes.Unecolorationpropred'ungrapheGest unefonctionas sociant `atoutsommetVdugrapheGunentie rrepr´esentantunecouleur dans[1,...,|V|],telleque deuxs ommetsadjacents n'aientpas lamˆemecouleur. Leprobl` emed'optimisationclassiqueestdetrouver unecolorationav ecunnom brede couleursminimum. Lenombrechromatiquecorrespond`acenombreminimal. D´efinition13(Nombrechromatique)Lenombrechromatiqued'ungraphe G(not´e χ(G))estle nombre minimumdec ouleursn´ecessaires pourlui donnerunec oloration propre. ˆetreNP-complet[GareyandJohnson, 1979].Malheure usement, pourun grapheg ´en ´eral, 31

32CHAPITRE4.COLORATION DEGRAPHES

lenombre chromatiqueχ(G)nep eutpasˆ etreapproxim´ea vecun facteurmultiplicatif |V|

1-ε

pourtoutε>0[Zuck erman,2007]saufsiP=NP.L'article[Zuc kerman,2007]

Onpeut consid´ererunalgorithme gloutonquia

ff ecteunec ouleurd'indicela plus petitepossible`a unsommetvenfonctiondes voisinsd ´ej` acolori´essuivan tl'ordredonn´e paruneliste dessommets deGarbitraire.E nfait,cetalgorithmeretourne unecoloration ayantunnombredecouleursauplus (G)+1. Ilest` anoterque cetalgorithmedonne unecoloration optimalepourlesgraphesd'in tervalle silalistedessommets est ordonn´ee enfonctionde l'ordrereoouleo. Deplusune bornec lassiques urlenombrechromatique estlasuivante[Brooks, 1941]. Th´eor`eme12([Brooks,1941])Pourtoutgr apheGdedegr ´emaximumΔ(G),ona Apartirde cer´ esultat,de nombreuxalgorithmes d'approximationont´et´ed´e velopp´ es (voir[Paschos, 2003]pourunsurvoldesr´ esultatsconnus pourceprobl`eme). Mais,ilf aut soulignerquele faitdeconna ˆıtredes propri´et ´essuppl ´ementairessurlegraphep ermet d'am´eliorerlefacteurd'approximation.En e ff et,parexemple, leprobl` emede trouver le nombrechromatiqueestappro ximable`aunfacteurm ultiplicatifO(|V| 3/14 log O(1) |V|)si legraphep oss`ede unecolorationproprede3couleurs(c'est-`a-direun graphe3-c oloriable) [Blum,1994]. Suite`a l'´etudedecettec oloration,d'autrescolorationsont´et ´e introduites commela

4.2Aprop osdel aa-coloration.

D´efinition14Unea-colorationestunec olorationpr opredesommetstellequechaque pairedecouleursposs` ededessommets adjacents. Lenombre a-chromatiqued'ungrapheGnot´eΨ(G)est lenombremaximumde cou- leurspour lequelGposs`edeunea-coloration.Parexemple dansungraphebiparticomplet moinsuncouplage parfaitK n,n ,lenom brea-chromatiqueestnc'est-`a-direlatailledela bipartition(voir lafigure4.2pourvis ualiserla a-colorationayant unnombredecouleurs maximum).

Leprobl` emeded´eterminersi

(G)≥kestNP-complet [YannakakisandGa vril,1980], mˆemepourlesarbres[Cairnie andKeith,1997],lesgraphes d'interv alleset lesco- graphes [Bodlaender,1989].Suite`a cesr´ esultatsde complexit´e,des algorithmesd'approxima- tionont ´et´epropos ´es:parexempleuneapproximation`afacteur2 pourlesarbres [KrystaandLory ´s,2006], etuneapproximation`afacteur O(nloglogn/logn)pour les grapheseng ´en ´eral[KortsarzandKrauthgamer,2001]. Despropri´ et´essurlenombrea-chromatiqueont´et ´e´etudi´ ees,notamment: Th´eor`eme13(HomomorphismInterpolationTheorem[Hararye tal.,1967]) colorationdekcouleurs.

4.3.APR OPOSDE LAB-COLORATION.33

Cettenotiond'in terpolation a´et´e´etudi´ee pourdi ff

´erentsparam`etres(voir[Harary ,1983]

pourunr´ecapitulatif ). Apartirde cettecoloration,et dupr´ ec´e dent th´ eor`eme, d'autrestypesdecolora- tionont ´et´ein troduitescommelab-coloration[IrvingandManlo ve,1999],puislaf- coloration[Dunbar etal.,2000].Les travaux surdescolorations desommets non-classiques ont´et´e initi´esparlaconstatationde[Kratoch v´ıletal.,2002]qu'unecolorationproprede sommets`a ccouleursd'ungraphe peuts etransformeren unecolorationutilisantc+1cou- leurs:il su ffi tsimplemen tdecolorierunsommetayan tunecoule urenune autrecouleur distincte.Par contred`esque l'onimposeunepropri´ et´esuppl´ementaire surlacoloration, ilestdi ffi ciledetransformer unecolorationde ccouleursenune autredec+1c ouleurs enconserv antlapropri´et´e,comme nousallonsle voir.

4.3Aprop osdel ab-coloration.

D´efinition15Uneb-colorationestunec olorationpr opredesommetstellequep our chaquecouleur, ilexisteunsommetde cettec ouleurquiest voisindesommets detoutes lesautres couleurs. Toutgrapheposs` edeune b-coloration:toutecolorationa yant unnombre minimalde couleursestune b-coloration.Eneffet,consid´erons unecolorationayantunnombremini- maldecouleurs. Pour chaquecouleur, siaucundesessommetsest levoisindesommets detoutesle sautres couleurs,alorsilsu ffi raitdele colorierdansune couleurnonpr ´esen te danssonv oisinage. Pourunecouleurc,lesommet vestunsommetb-chromatiquepourlacouleurcs'il estdec ouleurcetqu'ilest lev oisindes ommetsdetoutes lesautrescouleurs.Onappelle nombreb-chromatiquelenombremaxim umdecouleurs pourlequelungraphe admetune b-coloration. Leconcept deb-colorationa´et ´ein troduitdans[IrvingandManlove,1999].D´eterminer lenombre φ b (G)estNP-c ompleten g´en´eral [IrvingandManlo ve,1999]mˆemesilegraphe estbiparti[K ratoc hv´ıletal.,2002].Deplus,dans[Corteeletal.,2005],ila´et´ eprouv´e quesiP?=NP,iln'existe pasdeconstan te?>0pour laquellecalculerφ b (G)peut ˆetreapproxim´ e`aunfacteurmultiplicatifde120/133-?entempsp olynomial.Deplus, [KouiderandZak er,2006] ontdonn´edesbornes deφ b (G)enfonction dunombre de cliques. Parcontre,ceprobl `emedevientpolynomial pourles arbres[IrvingandManlove,1999], pourlesco-graphes[B onomoetal., 2009],etpourcertainsgraphes deKneser [JavadiandOmoomi,2009].P arcontre, ilestsurprenant quecettequestion resteencore ouvertepourlesgraphes d'intervalle,etpour lesgraphestriangul ´es. n'impliquepasune dec+1couleurs. Eneffet,l'hypercube dedimension3illustrecette remarque(voir figure4.1).Iladmetdeux b-colorations:unede 2couleurset unede

4couleurspuisqu'il estaus siungraphe biparticompletde8s ommetspriv´ed'un cou-

plageparfait.P arcontre, ilestfaciledev´ erifierqu'iln'admetpasde b-colorationdetrois couleurs.

Cesimplee xemplen'est pasuneexception.Ene

ff et,nousnous sommesint ´eress´ ees` a lanotionde b-spectred'ungraphedans[6].

34CHAPITRE4.COLORATION DEGRAPHES

1 1 1 1 2 2 2 2 1 2 3 4 1 2 3 4 b-colorationde2couleurs b-colorationde4couleurs

Fig.4.1-h ypercube etsesdeuxb-colorations

D´efinition16Unb-spectred'ungraphe Gcorrespond`al'ensembledesentierskpour Dans[6],nous avons prouv´e quetoutensembleIcorrespond`aungrapheGayantI commeb-spectre.Pourcela,pour toutensembleI?(N\{0,1})av ecmin(I)=2, un grapheGa´et ´econstruitdontleb-spectreS b (G)estI.Cette constructiondugrapheG sebase principalementsurlesgraphesbipartis completsmoinsuncouplageparfait.En e ff et,nousconsid´erons troiscas, enfonctiondunombred'´ el´eme ntsdeI. Cas1: PourI={2},ilsu ffitdepre ndreGquicorresp ond`auneseulearˆ eteouun graphebiparticomplet. Cas2: PourI={2,n},legraphe biparticomplet moinsuncouplage parfaitK n,n adeux b-colorationsdecouleurs2et n(voirfigure4.2). 2 2 2 2 2 2 1 1 1 1 1 1 1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6 b-colorationde2couleursb-colorationde6couleursar ˆetesn' ´etan tpasdans K 6,6

Fig.4.2-le grapheK

6,6 etses deuxb-colorations

Cas3: PourI={2,n

1 ,...,n p },av ec2Icommeb-spectreestungraphebipartiav ecn p ensemblesstablesdesommets d´efini commesuitG=(? p i=0 V i p i=1 E i )av ec(voirlafigure4.3): 1.V 0 ={v 1 0 ,...,v np 0 },V p ={v 1 p ,...,v np p

2.?i?{1,...,p-1},V

i ={v 1 i ,...,v n i -1 i p p ,[v 0 ,v j p ]?E p ?(??=j)

4.3.APR OPOSDE LAB-COLORATION.35

i p ,[v 0 ,v j i ]?E i ?(??=j)

5.?i?{1,...,p-1},??,[v

0 ,v 1 i ]?E i i -1) v 1 2 v 2 2 v 3 2 v 4 2 v 5 2 v 6 2 v 1 0 v 2 0 v 3 0 v 4 0 v 5 0 v 6 0 v 1 1 v 2 1 v 3 1

Fig.4.3-U ngraphea vecleb-spectre{2,4,6}

Pourconstruireuneb-colorationayant n

k couleurs,ilf auttoutd'ab orddonnerla couleuripourtouslessommets v i n k etv i 0 ,pour i?[1,...,n k -1].Ensuite,le ssommets v i 0 ,ont lacouleur1pour i?[n k ,...,n p ]ettous lesautre ssommetsson tdecouleur n k

Lafigure4.4 montreles di

´erentesb-colorationsdugrapheaussi donn´e.

L'id´eeprincipaledecettec onstructionestderendre b-chromatiquetouslessomme ts deV 0 .Pour r´ealisercela, etnotammentpourdesb-colorationsayan tunnombreinf´erieur`a n k ,l'astuceest queles sommets{v 1 1 ,...,v 1 n-k-1 }nesont pasadjacents`a touslessommets deV 0 afinqueplusie urssommetsde V 0 aurontlapossibilit´ ed'av oirlamˆemecouleur. 1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 4 4 4 4 4 1 2 3 1 1 1 1 2 3 b-colorationde6couleurs b-colorationde4couleurs Fig.4.4-U ngraphea vecleb-spectre {2,4,6}etses b-colorations Cetteconstruction fournitungrapheay antIcommespectre pourtoutensemble d'en- tiersI?(N\{0,1})av ecargmin(I)=2. Pourenle ver lacontrainteI?(N\{0,1})av ec min(I)=2, ilsu ffitder ´ealiserune op´erationdetranslation:`apartir d'ungraphe H, onobtien tungrapheGcorrespondant`al'uniondecegrapheet d'ungrapheK x complet

36CHAPITRE4.COLORATION DEGRAPHES

1 2 1 2 3 1 2 3 4 5 ungraphea yant {2}ungraphecomple tungraphe ayant{5}commeb-spectre. commeb-spectre.de3sommets

Fig.4.5-op ´erationde translation

`axsommets.Tous lessommetsdeHserontadjacents`a touslessommetsdeK x .Cette constructionimpliquequ'ilexisteune b-colorationdeicouleursdansHsietse ulement s'ilexis teuneb-colorationdei+xcouleursdansG.Lafigure 4.5illustrece ttetranslation. Parcontre,cette constructionnedonnepasungrapheGayantunnombreminimumde sommetsoud'ar ˆetesa yantIcommeb-spectre.Parexemple,pourle graphedessin´edans lafigure4.3, ilsu ffi tdesupprimer l'ensemble desarˆ etes{(v j 0 ,v i 1 pourobtenirungraphea yan t{2,4,5,6}commespectre. Parcontre,pour obtenirun grapheav ecuntelspectre,notrec onstructiondoitra jouterdes sommetsdesarˆetesetdes sommets.Unequestion naturellese pose alors:quels sontlesgraphes ayantunnombre minimumdesommetsoud'ar ˆetes pourun spectre donn´e? Deplus,une questionnaturelle quisuit` acespr ´ec´edents travaux estdecomprendre lastructuredes graphesquion tunin tervallecomme b-spectre.Cesprobl`emessont li´es auxprobl` emesd'interpolationde[Hararyetal.,1967] pourlesa-colorations.Plusformel- lement,quelestlet ypede graphedont leb-spectreestunintervalle ? D´efinition17(Grapheb-continu)Ungraphe estb-continusietseulement sisonb- spectreestcompos´euniquementd'entiers cons´ ecutifs. D´eterminersiGestb-continuestNP-complet[6].Ceprobl `emeresteaussidi fficile mˆemesiuneb-colorationdeχ(G)couleurs etuneb-colorationdeb(G)couleurs deGsont donn´ees.Deplus,cer´esultat a´et ´e´ etendu`alaclasse degraphesbipartis[Faik,2005].quotesdbs_dbs5.pdfusesText_9

[PDF] Chapitre 4 Coloration de graphes

Coloration dun graphe - Meilleur en Maths

VI Coloration de graphe - math-baudon