Coloration forte

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.

En théorie des graphes, une coloration forte, avec une partition des sommets en sous-ensembles (disjoints) de même taille, est une (bonne) sommet de coloriage dans laquelle chaque couleur apparaît exactement une fois dans chaque partition. 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.

Le nombre chromatique fort sx(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 nombre chromatique fort k.

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

1. sx(G) > Δ(G).
2. sx(G) ≤ 3 Δ(G) − 1 (Haxell)
3. Asymptotiquement, sx(G) ≤ 11 Δ(G) / 4 + o(Δ(G)). (Haxell)

Ici Δ(G) est le degré maximal.

La notion de nombre chromatique fort a été introduite indépendamment par Alon (1988) et Fellows (1990).

Références

• 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).