Coloration forte

En théorie des graphes, une coloration forte est une coloration de graphe dans laquelle chaque couleur apparaît exactement une fois dans chaque partition, avec une partition des sommets en sous-ensembles (disjoints) de même taille.

Cette échelle de Möbius est fortement 4-colorable. Il y a 35 partitions de taille 4, mais seules ces 7 partitions sont topologiquement distinctes.

Lorsque l'ordre du graphe G n'est pas divisible par k, on ajoute des sommets isolés à G juste assez pour rendre l'ordre de ce nouveau graphe G' divisible par k. Dans ce cas, une forte coloration de G' moins les sommets isolés ajoutés précédemment est considérée comme une forte coloration de G. Un graphe est fortement k-colorable si, pour chaque partition des sommets en deux ensembles de taille k, il admet une coloration forte.

L' indice chromatique fort sχ(G) d'un graphe G est le plus petit nombre k tel que G est fortement k-colorable. Un graphe est fortement k-chromatique s'il a pour indice chromatique fort k.

Certaines propriétés de sx(G):

1. sχ(G) > Δ(G).
2. sχ(G) ≤ 3 Δ(G) - 1 (Haxell)
3. Asymptotiquement, sχ(G) ≤ 11 Δ(G) / 4 + o(Δ(G)). (Haxell)

Ici Δ(G) est le degré maximal.

La notion d'indice chromatique fort a été introduite indépendamment par Noga Alon (1988) et Michael Fellows (1990).

Références

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Strong coloring » (voir la liste des auteurs).

Bibliographie

• Noga Alon, « The linear arboricity of a graph », Israel J. Math., vol. 62, n^o 3,‎ 1988, p. 311–325 (DOI 10.1007/BF02783300)
• Noga Alon, « The strong chromatic number », Random Structures and Algorithms, vol. 3,‎ 1992, p. 1–7 (DOI 10.1002/rsa.3240030102)
• Michael R. Fellows, « Transversals of vertex partition in graphs », SIAM Journal on Discrete Mathematics, vol. 3, n^o 2,‎ 1990, p. 206–215 (DOI 10.1137/0403018)
• P.E. Haxell, « On the strong chromatic number », Combinatorics, Probability and Computing, vol. 13,‎ 2004, p. 857–865 (DOI 10.1017/S0963548304006157)
• Jensen, Tommy R.; Toft, Bjarne (1995). Graphique coloration des problèmes. New York: Wiley-Interscience. (ISBN 0-471-02865-7).
• Hervé Hocquard. « Colorations de graphes sous contraintes ». Mathématique discrète [cs.DM]. Université Sciences et Technologies - Bordeaux I, 2011. Français. En ligne <tel-00987686>.