Homomorphismes et Colorations de Graphes

Plan du coursChapitre 1. Coloration de graphes .................................................................... 3

1.1. Définitions de base ...................................................................................... 3 1.2. Quelques résultats de base ......................................................................... 4 1.3. Graphes planaires ........................................................................................ 5 1.4. Graphes critiques ......................................................................................... 7 1.5. Graphes parfaits .......................................................................................... 8 1.6. Polynômes chromatiques ............................................................................. 9

Chapitre 2. Homomorphismes de graphes .................................................... 13 2.1. Homomorphismes et colorations ............................................................... 13 2.2. Hiérarchie des classes de coloration ......................................................... 14

 

Bibliographie[BO] Béla Bollobás, Modern Graph Theory, Graduate Texts in

Mathematics 184, Springer (1998), Chap. V : Colouring, pp. 145-180.[BE] Claude Berge, Graphes et hypergraphes, Dunod, 2ème édition (1973),

Chap. 15 : Nombre chromatique, pp. 314-346, Chap. 16 : Graphes parfaits, pp. 347-370, Chap. 12 : Indice chromatique, pp. 236-259.

[JT] Tommy R. Jensen and Bjarne Toft, Graph Coloring Problems, Wiley-Interscience Series in Discrete Mathematics and Optimization (1995).

[NW] Roy Nelson and Robin J. Wilson (Eds), Graph Colourings, Pitman Research Notes in Mathematics Series 218, Longman (1990).

[T] Bjarne Toft, Colouring, stable sets and perfect graphs, in Handbook of Combinatorics, vol. I (Graham, Grötschel and Lovász eds), North-Holland (1995), pp. 233-288.

Chapitre 1.Chapitre 1.           Coloration de graphes

1.1.1.1.      Définitions de baseDéfinition 1. Définition 1.       Une k-coloration (k-coloring) d’un graphe G est

une application c : V(G) ® C, où C est un ensemble de k couleurs (généralement, C = {1,2,…,k}), telle que pour toute arête uv de E(G), c(u) ¹ c(v). Un graphe qui admet une k-coloration est dit k-coloriable (k-colorable).

Définition 2. Définition 2.       Si c est une k-coloration de G et i, 1 £ i £ k, une couleur, alors c-1(i) est une classe de couleur (color-class).

Définition 3. Définition 3.       Le nombre chromatique (chromatic number) c(G) d’un graphe G est le plus petit entier k tel que G admet une k-coloration. Si c(G) = k, le graphe G est dit k-chromatique (k-chromatic).

On constate aisément que toute coloration d’un graphe contenant une clique de taille k nécessite au moins k couleurs. Plus précisément :Proposition 1. Proposition 1.           Pour tout graphe G, c(G) ³ w(G).

où w(G) désigne la taille maximale d’une clique dans G (clique number).De la même façon, chaque classe de coloration étant un stable, nous avons :Proposition 2. Proposition 2.           Pour tout graphe G à n sommets, c(G) ³

n / a(G).

où a(G) désigne le nombre de stabilité de G (independence or stability number) (c’est-à-dire la taille maximale d’un ensemble stable).Considérons un graphe G à n sommets et ordonnons ses sommets de façon quelconque : V(G) = {v1, v2, …, vn}. Prenons l’ensemble C = {1, 2, …} comme ensemble de couleurs. Un algorithme simple de coloration, glouton (dit algorithme First-Fit), est alors le suivant :                colorions les sommets dans l’ordre v1, v2, …, vn,                pour colorier le sommet vi, utilisons la plus petite couleur possible

(en d’autres termes, affectons à vi la plus petite couleur non encore utilisée par les voisins de vi déjà coloriés).

Clairement, cet algorithme produit une coloration de G utilisant au maximum D(G)+1 couleurs… Ainsi :Proposition 3. Proposition 3.           Pour tout graphe G, c(G) £ D(G) + 1.

Finalement, pour tout graphe G à n sommets, nous avons :max { w(G), n / a(G) } £ c(G) £ D(G) + 1.

Exercices.[exo 1]. [exo 1].           Trouvez un graphe G pour lequel w(G) > n / a(G).[exo 2]. [exo 2].           Trouvez un graphe G pour lequel w(G) < n / a(G).[exo 3]. [exo 3].           Trouvez un graphe G pour lequel w(G) = n / a(G).[exo 4]. [exo 4].           Trouvez un graphe G pour lequel w(G) = D(G) + 1.[exo 5]. [exo 5].           Montrez que pour tout graphe G, il est possible

d’ordonner les sommets de G de façon telle que l’algorithme First-Fit produit une coloration de G utilisant c(G) couleurs.

1.2.1.2.      Quelques résultats de baseThéorème 1. Théorème 1.        Un graphe G est 2-chromatique si et

seulement si il contient au moins une arête et ne contient aucun cycle impair (graphe biparti non vide).

Nous avons vu précédemment que pour tout graphe G, c(G) £ D(G) + 1. Le résultat suivant caractérise les graphes pour lesquels nous avons l’égalité.Théorème 2. Théorème 2.        [Brooks1[1], 1941] Soit G un graphe de degré

maximal D. Nous avons alors c(G) = D + 1 si et seulement si D = 2 et l’une des composantes connexes de G est un cycle impair ou D ¹ 2 et l’une des composantes connexes de G est une clique d’ordre D + 1. (Dans le cas contraire, nous avons c(G) £ D).

La borne donnée par le théorème de Brooks peut être améliorée en considérant le degré minimum des sous-graphes induits :Théorème 3. Théorème 3.        [Halin, 1967] Soit G un graphe et k = maxH {

d(H) : H sous-graphe induit de G }. Nous avons alors c(G) £ k + 1 (en d’autres termes, si G est k-dégénéré, c(G) £ k + 1).

Nous avons vu précédemment que pour tout graphe G, c(G) ³ w(G). On peut naturellement se demander si la présence de cliques dans un graphe

1 [1] R.L. Brooks, On colouring the nodes of a network, Proc. Cambreidge Phil. Soc. 37 (1941), 194-197.

est nécessaire pour que le graphe ait un nombre chromatique élevé… La réponse est non, comme le montre le résultat suivant :Théorème 4. Théorème 4.        [Zykov, 1949] Pour tout k, il existe des

graphes k-chromatiques ne contenant pas de triangle (triangle-free graph).

Ce résultat a été renforcé par Erdös qui, à l’aide d’une preuve probabiliste (non constructive) montra :Théorème 5. Théorème 5.        [Erdös, 1961] Pour tous k et l, il existe un

graphe k-chromatique de maille au moins l (c’est-à-dire sans cycle de longueur inférieure à l).

Des preuves constructives ont été proposées par la suite : Lovàsz (1968), Nesetril et Rödl (1979).

1.3.1.3.      Graphes planairesDéfinition 4. Définition 4.       Un graphe G est planaire s’il peut être

représenté sur le plan (ou sur la sphère) de façon telle que ses arêtes ne se coupent pas (en dehors de leurs sommets extrémités). Une face est une région connexe du plan délimitée par des arêtes (la face « extérieure » est infinie sur le plan, les faces sont toutes finies sur la sphère).

Définition 5. Définition 5.       Une subdivision (subdivision) d’un graphe H est un graphe H’ obtenu en « plaçant » sur chaque arête de H 0, 1 ou plusieurs sommets de degré 2.

Une caractérisation des graphes planaires est donnée par le résultat suivant :Théorème 6. Théorème 6.        [Kuratowski2[2], 1930] Un graphe G est

planaire si et seulement si il ne contient pas de subdivision de K3,3 ou de K5.

La formule suivante permet d’obtenir des propriétés intéressantes sur la structure des graphes planaires :

[Formule d’Euler] Si G est un graphe planaire connexe ayant n À l’aide de cette formule, on obtient par exemple :Proposition 4. Proposition 4.           Un graphe planaire à n sommets, n ³ 3,

possède au plus 3n-6 arêtes.

De la même façon, nous avons :2 [2] K. Kuratowski, Sur le problème des courbes gauches en topologie, Fund. Math. 15

(1930), 271-283.

Proposition 5. Proposition 5.           Tout graphe planaire contient un sommet de degré au plus 5.

Le résultat précédent signifie que tout graphe planaire est 5-dégénéré. D’après le théorème de Halin, tout graphe planaire est donc 6-coloriable.Définition 6. Définition 6.       Le dual (dual graph) d’un graphe planaire G est

le graphe planaire dont les sommets sont les faces de G, deux faces étant adjacentes lorsqu’elles ont une arête commune (on vérifie aisément que le dual est planaire…).

Exercices.[exo 6]. [exo 6].           En utilisant la formule d’Euler, montrer que le graphe

K5 n’est pas planaire.[exo 7]. [exo 7].           En utilisant la formule d’Euler, montrer que le graphe

K3,3 n’est pas planaire.[exo 8]. [exo 8].           En utilisant la formule d’Euler, montrer qu’un ballon de

football, composé d’hexagones et de pentagones, contient nécessairement 12 pentagones.

[exo 9]. [exo 9].           Montrer qu’un graphe planaire à n sommets, n ³ 3, ne contenant pas de triangles, possède au maximum 2n-4 arêtes.

En 1879, Kempe proposa une preuve de la conjecture des quatre couleurs. En 1890, Heawood montra que cette preuve était erronée et, en utilisant les arguments de Kempe, prouva le résultat suivant :Théorème 7. Théorème 7.        [Heawood3[3], 1890] Tout graphe planaire est

5-coloriable.

Dans le même article, Heawood propose une solution du « problème des n couleurs » pour toutes les surfaces orientables de genre non nul. Mais sa démonstration était erronée… elle fut achevée par Ringel et Youngs en 1968.Définition 7. Définition 7.       Une surface orientable de genre (genus) g est

homéomorphe à une sphère possédant g « trous » (handles). Le genre d’un graphe G est alors le genre minimum d’une surface sur laquelle G est représentable (c’est-à-dire peut être dessiné sans croisement d’arêtes). Une surface orientable de genre 1 est un tore (torus).

Théorème 8. Théorème 8.        [Heawood, 1890, Ringel and Youngs4[4], 1968] Tout graphe de genre g ³ 1 peut être colorié en utilisant H(g)

3 [3] P.J. Heawood, Map colour theorem, Quart. J. Pure Appl. Math. 24 (1890), 332-338.4 [4] G. Ringel and J.W.T. Youngs, Solution of the Heawood map-coloring problem,

Proc. Natl. Acad. Sci. USA 60 (1968), 438-445.

couleurs, avec H(g) = ë(7 + sqrt(1 + 48g)) / 2û (ce nombre est appelé nombre de Heawood).

La conjecture des quatre couleurs a été démontrée par Appel et Haken en 1976 :Théorème 9. Théorème 9.        [Appel and Haken5[5], 1976] Tout graphe

planaire est 4-coloriable.

Cette preuve est basée sur l’idée suivante :                il existe un ensemble de 1482 configurations inévitables

(unavoidable), c’est-à-dire tel que tout graphe planaire triangulé contient nécessairement l’une de ces configurations comme sous-graphe,

               ces configurations sont réductibles, c’est-à-dire qu’une 4-coloration d’un graphe planaire contenant l’une de ces configurations peut toujours être obtenue à partir d’une 4-coloration d’un graphe planaire « plus petit »… (en d’autres termes, un contre-exemple minimal pour la conjecture des quatre couleurs ne peut pas contenir l’une de ces configurations).

Le graphe K4 étant planaire, la borne de 4 pour le nombre chromatique des graphes planaires est naturellement optimale… En 1959, Grötzsch montra que les triangles étaient « nécessaires » à la 4-coloriabilité des graphes planaires :Théorème 10. Théorème 10.   [Grötzsch6[6], 1959] Tout graphe planaire sans

triangle est 3-coloriable.

Ce résultat a été amélioré par Aksionov en 1974 :Théorème 11. Théorème 11.   [Aksionov7[7], 1974] Tout graphe planaire

contenant au plus trois triangles est 3-coloriable.

1.4.1.4.      Graphes critiquesDéfinition 8. Définition 8.       Un graphe G est dit critique (critical) si pour

tout sommet x de G nous avons c(G-x) < c(G).

Les propriétés suivantes des graphes critiques sont faciles à obtenir :

5 [5] K. Appel and W. Haken, Every planar map is four-colorable, Part I  : Discharging, Illinois J. of Math. 21 (1977), 429-490, et K. Appel, W. Haken and J. Koch, Every planar map is four-colorable, Part II : Reducibility, Illinois J. of Math. 21 (1977), 491-567.

6 [6] H. Grötzsch, Ein Dreifarbensatz für dreikreisfreie Netze auf der Kugel, Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe 8 (1959), 109-120.

7 [7] V.A. Aksionov, On continuation of 3-coloring of planar graphs (in Russian), Metody Diskret. Analiz. 26 (1974), 3-19.

               Tout graphe k-chromatique G contient un sous-graphe critique k-chromatique.

               Un graphe critique est connexe.

               Si G est un graphe critique, alors d(G) ³ c(G) - 1.

               Un graphe critique G ne contient aucune clique qui soit un ensemble d’articulation (on en déduit notamment que G est biconnexe).

Le résultat suivant est une généralisation du théorème de Brooks :Théorème 12. Théorème 12.   [Gallai, 1963] Si G est un graphe critique, le

sous-graphe de G engendré par les sommets de degré c(G) - 1 est tel que chacune de ses composantes biconnexes est soit une clique soit un cycle impair.

Exercice.[exo 10]. [exo 10].      Montrez que ce résultat implique le théorème de

Brooks.

1.5.1.5.      Graphes parfaitsNous avons vu (théorèmes de Zykov et de Erdös) que la présence de cliques de grande taille dans un graphe n’était pas une condition nécessaire pour que le nombre chromatique du graphe soit élevé. À l’opposé de cette situation, se trouvent les graphes parfaits :Définition 9. Définition 9.       Un graphe G est parfait (perfect graph), si pour

tout sous-graphe induit H de G nous avons c(H) = w(H).

Définition 10. Définition 10.  Un graphe G est un graphe de comparabilité s’il est possible d’orienter ses arêtes de façon telle que le graphe orienté (antisymétrique) ainsi obtenu soit transitif (si uv et vw sont deux arcs, alors uw est un arc).

Définition 11. Définition 11.  Un graphe G est un graphe d’intervalles si on peut associer à chacun de ses sommets un intervalle d’entiers de façon telle que deux sommets sont reliés par une arête si et seulement si leurs intervalles ont une intersection non vide.

Exercices.[exo 11]. [exo 11].      Montrer que les graphes de comparabilité sont parfaits.[exo 12]. [exo 12].      Montrer que le complémentaire d’un graphe

d’intervalles est un graphe de comparabilité.

La notion de graphe parfait a été introduite par C. Berge en 1961 et a donné lieu depuis à de très nombreux travaux de recherche. C. Berge a conjecturé qu’un graphe était parfait si et seulement si son complémentaire était parfait (conjecture faible des graphes parfaits). Cette conjecture a été démontrée par Lovàsz en 1972. La preuve nécessite le résultat préalable suivant :Théorème 13. Théorème 13.   [Lovàsz8[8], 1972] Soit G un graphe parfait et x

un sommet de G. Soit H le graphe obtenu en remplaçant x par une clique C reliée complètement aux voisins de x. Le graphe H ainsi obtenu est parfait.

Le résultat de Lovasz peut alors s’énoncer :Théorème 14. Théorème 14.   [Lovàsz, 1972] Un graphe G est parfait si et

seulement si le complémentaire de G est parfait.

Si H est un sous-graphe induit d’un graphe parfait, nous avons :w(H) = c(H) ³ |V(H)| / a(H) = |V(H)| / w(H-).

Ainsi, pour tout sous-graphe induit H d’un graphe parfait, |V(H)| £ w(H)w(H-). Lovàsz prouva en 1972 que cette condition était également suffisante :Théorème 15. Théorème 15.   [Lovàsz9[9], 1972] Un graphe G est parfait si et

seulement si pour tout sous-graphe induit H de G, |V(H)| £ w(H)w(H-).

La conjecture forte des graphes parfaits a été récemment démontrée :Théorème 16. Théorème 16.   [Chudnovsky, Robertson, Seymour et

Thomas, 2002] Un graphe G est parfait si et seulement si ni lui ni son complémentaire ne contiennent de cycle impair induit de longueur au moins cinq.

1.6.1.6.      Polynômes chromatiquesDéfinition 12. Définition 12.  Pour tout graphe G, on note P(G,l) le nombre

de l-colorations (utilisant l’ensemble {1, 2, …, l} comme ensemble de couleurs, sans nécessairement les utiliser toutes…). P(G,l) est le polynôme chromatique (chromatic polynomial) du graphe G.

Remarques.

8 [8] L. Lovàsz, Normal hypergraphs and the perfect graph conjecture, Discrete Math. 2 (1972), 253-267.

9 [9] L. Lovàsz, A characterization of perfect graphs, J. Combin. Theory B 13 (1972), 95-98.

               Par définition, pour tout graphe G, P(G,l) = 0 si l < c(G) et P(G,l) > 0 si l ³ c(G) (voir exemples précédents).

               Le théorème des quatre couleurs peut être reformulé ainsi : si G est un graphe planaire, alors P(G,4) ¹ 0…

Soit G un graphe et e une arête de G. Notons G-e le graphe obtenu en supprimant l’arête e et G*e le graphe obtenu en contractant l’arête e (c’est-à-dire en identifiant les sommets extrémités de e, et en simplifiant le cas échéant les arêtes multiples et les boucles ainsi obtenues).Nous avons alors :Proposition 6. Proposition 6.           Si G un graphe et e une arête de G,

alors P(G,l) = P(G-e,l) - P(G*e,l).

Cette formule fournit une méthode de calcul récursive de P(G,l) pour tout graphe G :

       si G est vide et possède n sommets, P(G,l) = ln,        sinon, soit uv une arête de G, calculons P(G-e,l) et P(G*e,l)…

On déduit facilement de cet algorithme les propriétés suivantes :Proposition 7. Proposition 7.           Si G est un graphe à n sommets et m

arêtes, alors :           P(G,l) est un polynôme de degré n,           le coefficient de ln est 1,           le coefficient de ln-1 est -m,           il n’y a pas de terme constant (P(G,0) = 0),           le coefficient de ln-j est positif si et seulement si j est

pair.Exercice.

[exo 13]. [exo 13].      Prouver la proposition précédente.Soit maintenant G un graphe et u et v deux sommets non voisins de G. Notons G+uv le graphe obtenu en rajoutant l’arête uv et G*uv le graphe obtenu en fusionnant les sommets u et v. En « retournant » la formule précédente, nous obtenons :Proposition 8. Proposition 8.           Si G un graphe et u et v deux sommets

non voisins de G, alors P(G,l) = P(G+uv,l) + P(G*uv,l).

Cette formule fournit une deuxième méthode de calcul pour P(G,l). Cette fois, les graphes « terminaux » sont des graphes complets. Le polynôme est alors obtenu sous forme d’une somme de polynômes chromatiques de graphes complets (on notera l(n) = l(l-1)…(l-n+1) = l!/(l-n)! le polynôme

chromatique de Kn). L’expression du polynôme chromatique ainsi obtenu est dite sous forme factorielle (factorial form), par opposition à la forme usuelle (usual form).Ces deux procédés de calcul sont appelés des réductions chromatiques.Les propositions suivantes peuvent permettre de « simplifier » le calcul du polynôme chromatique d’un graphe.Proposition 9. Proposition 9.           Si le graphe G possède k composantes

connexes G1, G2, …, Gk, alors P(G,l) = P(G1,l) x P(G2,l) x … x P(Gk,l).

Proposition 10. Proposition 10.      Si le graphe G est composé de deux sous-graphes G1 et G2 ayant pour intersection une clique de taille k, alors :

P(G, l) = [ P(G1, l) x P(G2, l) ] / l(k)

On appelle produit de deux graphes G et H le graphe obtenu à partir de copies disjointes de G et H en reliant tout sommet de G à tout sommet de H.Proposition 11. Proposition 11.      Si G est le produit de deux graphes G1 et

G2, alors P(G, l) = P(G1, l) Ä P(G2, l),

où Ä désigne le produit dans lequel les formes factorielles sont traitées comme des puissances (l(a) Ä l(b) = l(a+b)).

Exercices.[exo 14]. [exo 14].      Montrer qu’un graphe G à n sommets est un arbre si et

seulement si P(G,l) = l(l-1)n-1.[exo 15]. [exo 15].      Déterminer le polynôme chromatique des deux

graphes suivants. Que remarque-t-on ?

Le résultat suivant donne une interprétation des coefficients du polynôme chromatique d’un graphe, sous sa forme usuelle ou factorielle :Théorème 17. Théorème 17.   Pour tout graphe G à n sommets et m arêtes,

nous avons :

        Le coefficient de l(k) dans la forme factorielle de P(G,l) est PG(k), correspondant au nombre de façons de partitionner les sommets de G en exactement k stables.

        Le coefficient de lk dans la forme usuelle de P(G,l) est sumr=0,m { (-1)r N(k,r) }, où N(k,r) représente le nombre de sous-graphes de G ayant r arêtes et k composantes connexes.

Ainsi,

P(G,l) =

n

k 1 { PG(k) x l(k) } =

n

k 1 {

m

r 0 { (-1)r N(k,r)} } x lk

Chapitre 2.Chapitre 2.           Homomorphismes de graphes

2.1.2.1.      Homomorphismes et colorationsDéfinition 13. Définition 13.  Un homomorphisme d’un graphe G vers un

graphe H est une application h de V(G) vers V(H) qui préserve les arêtes : uv Î V(G) Þ h(u)h(v) Î V(H).

Définition 14. Définition 14.  On dit qu’un graphe G est H-coloriable, noté G ® H, s’il existe un homomorphisme de G vers H. Si, de plus, H est G-coloriable, nous disons que G et H sont hom-équivalents, noté G « H. Nous noterons G /® H le fait qu’un graphe G n’est pas H-coloriable.

Proposition 12. Proposition 12.      Un graphe G est k-coloriable si et seulement si G ® Kk.

Proposition 13. Proposition 13.      Un graphe G est k-chromatique si et seulement si G ® Kk et G /® Kk-1.

La composition de deux homomorphismes étant un homomorphisme, la relation ® est transitive. Ainsi, si H1 est un sous-graphe de H2 (nous avons alors H1 ® H2), pour tout graphe G, G ® H1 implique G ® H2. Pour certains des sous-graphes de H2 (en particulier pour H2 lui-même), l’implication inverse est également vérifiée.Plus précisément :Définition 15. Définition 15.  Un graphe H est hom-minimal si pour tout

sous-graphe propre H’ de H nous avons H /® H’ (en d’autres termes, tout homomorphisme de H dans H est un automorphisme).

Définition 16. Définition 16.  Un sous-graphe H* d’un graphe H est une hom-contraction (core) de H si H ® H* et H* est hom-minimal (notons que dans ce cas H et H* sont hom-équivalents).

Proposition 14. Proposition 14.      Si H* est une hom-contraction de H, alors pour tout graphe G, G ® H Û G ® H*.

Proposition 15. Proposition 15.      À isomorphisme près, tout graphe admet une unique hom-contraction.

Pour terminer cette partie, nous allons donner un résultat qui va nous permettre d’illustrer les techniques mises en œuvre dans la preuve du théorème des quatre couleurs. Nous avons pour cela besoin de la définition suivante :Définition 17. Définition 17.  Le degré moyen (average degree) dm(G) d’un

graphe G est donné par dm(G) = 2e(G) / v(G). Le degré moyen maximum (maximum average degree) dmm(G) d’un graphe G est le maximum des degrés moyens de ses sous-graphes : dmm(G) = max { dm(H) : H Í G }.

Proposition 16. Proposition 16.      Si G est un graphe sans triangle de degré moyen maximum strictement inférieur à 9/4, alors G ® C5.

En fait, en « travaillant un peu plus », on peut améliorer le résultat précédent :Proposition 17. Proposition 17.      Si G est un graphe sans triangle de

degré moyen maximum strictement inférieur à 7/3, alors G ® C5.

Dans le cas des graphes planaires, le degré moyen maximum d’un graphe est relié à la maille du graphe de la façon suivante :Proposition 18. Proposition 18.      Soit G est un graphe planaire de maille

g. Nous avons alors dmm(G) < 2g / (g-2).

Notre résultat sur la C5-colorabilité admet donc pour corollaire, dans le cas des graphes planaires :Corollaire 1. Corollaire 1.          Tout graphe planaire de maille au moins 14

est C5-coloriable.

2.2.2.2.      Hiérarchie des classes de colorationDéfinition 18. Définition 18.  Pour tout graphe H, on note [H] l’ensemble des

graphes H-coloriables : [H] = { G / G ® H }. Cet ensemble [H] est une classe de coloration (plus précisément, la classe de coloration de H).

La propriété suivante indique que nous pouvons toujours choisir comme représentant (unique) d’une classe de coloration un graphe hom-minimal.Proposition 19. Proposition 19.      Pour tout graphe H, il existe un unique (à

isomorphisme près) graphe hom-minimal H’ tel que [H] = [H’].

Un ordre partiel sur les classes de coloration est donné par la relation d’inclusion (on notera Í la relation d’inclusion au sens large et Ì la relation de stricte inclusion). Cet ordre va nous permettre de définir la hiérarchie des classes de coloration.Les propriétés suivantes découlent directement de la définition :Proposition 20. Proposition 20.      Nous avons :

          [G] Í [H] si et seulement si G ® H,           [G] Ì [H] si et seulement si G ® H et H /® G,           [G] = [H] si et seulement si G « H.

La propriété suivante va nous être utile pour « ordonner » les classes de coloration :Proposition 21. Proposition 21.      Si H1 et H2 sont deux graphes tels que

H1 ® H2, alors c(H1) £ c(H2) et og(H1) ³ og(H2) (maille impaire).

Considérons maintenant les classes de colorations dont les représentants sont les graphes complets. Nous avons clairement :

[K1] Ì [K2] Ì … Ì [Kk] Ì [Kk+1] Ì …Les cycles s’insèrent aisément dans cette hiérarchie :

[K1] Ì [K2] = [C2p] Ì … [C2p+1] Ì [C2p-1] Ì … Ì [C3] = [Kk] Ì [Kk+1] Ì …Exercices.

[exo 16]. [exo 16].      Appelons « fleur » (à 2n+1 pétales de taille 2m+1) le graphe Fn,m obtenu en « arrangeant » 2n+1 cycles de taille 2m+1 comme indiqué ci-dessous :

La fleur F(1,3) La fleur F(2,2)

Montrer que nous avons la sous-hiérarchie suivante pour tout m :

[C2m+1] = [F0,m] Ì … Ì [Fn+1,m] Ì [Fn,m] Ì … Ì [F0,m-1] = [C2m-1]

[exo 17]. [exo 17].      Montrer que si G est hom-minimal, alors le graphe G+k, obtenu en rajoutant une clique de taille k reliée à tous les sommets de G est également hom-minimal.En déduire que la sous-hiérarchie des cycles impairs et des fleurs, située entre [K2] et [K3] peut être « transportée » entre [Kk] et [Kk+1] pour tout k ³ 3.

Deux questions naturelles se posent alors :                cette hiérarchie est-elle linéaire, c’est-à-dire deux classes de

coloration [G1] et [G2] sont-elles toujours comparables ([G1] Í [G2] ou [G2] Í [G1]) ?

               cette hiérarchie est-elle dense, c’est-à-dire existe-t-il pour tous graphes G1 et G2 tels que [G1] Ì [G2] un graphe G3 tel que [G1] Ì [G3] Ì [G2] ?

Nous avons en réalité les éléments nous permettant de répondre, de façon négative, à la première question :Théorème 18. Théorème 18.   Pour tout p ³ 2, il existe une famille de p

graphes dont les classes de colorations sont deux à deux incomparables.

Pour ce qui est de la densité, la question est plus complexe. Regardons le début de notre hiérarchie, [K1] Ì [K2]. Un graphe G est dans [K1] si et seulement si il ne contient aucun arête. Dès qu’il contient une arête, nous avons nécessairement K2 ® G et donc [K2] Í [G]. Ainsi, aucune classe de couleur n’est comprise strictement dans l’intervalle [K1,K2]. Nous disons que cette paire de graphes constitue un saut (gap) dans la hiérarchie.En 1982, Welzl a montré qu’il s’agissait là du seul saut présent dans la hiérarchie des classes de couleurs qui, à cette exception près, est donc dense.Théorème 19. Théorème 19.   [Welzl10[10], 1982] Pour toute paire de graphes

hom-minimaux (G1,G2) ¹ (K1,K2), telle que [G1] Ì [G2] il existe un graphe G3 tel que [G1] Ì [G3] Ì [G2].

10 [10] E. Welzl, Color-families are dense, Theoret. Comput. Sci. 17 (1982), 29-41.