Graphe à coloration unique

En théorie des graphes, un graphe à coloration unique est un graphe qui possède une et une seule ${\displaystyle k}$-coloration, à une permutation des couleurs près. De façon équivalente, il n'existe qu'une seule partition de ses sommets en ${\displaystyle k}$ ensembles indépendants, et il n'existe pas de partition en ${\displaystyle k-1}$ ensembles indépendants.

Un graphe complet est à coloration unique, car la seule coloration est celle qui attribue à chaque sommet une couleur différente.

Un k-arbre est ${\displaystyle k-1}$-colorable de manière unique. Les graphes planaires uniquement 4-colorables sont exactement les réseaux apolliniens (en), c'est-à-dire les 3-arbres planaires^[1].

Tout graphe biparti connexe est bicolorable de manière unique. Cette bicoloration peut être obtenue en choisissant arbitrairement un sommet de départ, en colorant les sommets à distance paire de ce sommet avec une couleur et en colorant les sommets à distance impaire de ce sommet avec l'autre couleur^[2].

Un graphe ${\displaystyle G}$ uniquement ${\displaystyle k}$-colorable à ${\displaystyle n}$ sommets possède au moins ${\displaystyle (k-1)n-k(k-1)/2}$ arêtes. L'égalité est vérifiée lorsque ${\displaystyle G}$ un ${\displaystyle k}$-arbre.

Un graphe imparfait minimal est un graphe dont chaque sous-graphe est parfait. La suppression d'un sommet d'un graphe imparfait minimal donne un sous-graphe à coloration unique.

Un graphe à arêtes colorables de manière unique est un graphe à arêtes colorables qui possède une et une seule coloration des arêtes en ${\displaystyle k}$ couleurs, à une permutation des couleurs près. Les seuls graphes à arêtes 2-colorables de manière unique sont les chemins et les cycles. Les étoiles ${\displaystyle S_{k}}$ sont à arêtes k-colorables de manière unique. Wilson (1976)^[3] a conjecturé et Thomason (1978)^[4] a prouvé que pour ${\displaystyle k\geq 4}$, elles sont également les seuls éléments de cette famille. Cependant, il existe des graphes à arêtes colorables de manière unique qui n'entrent pas dans cette catégorie, comme le graphe de la pyramide triangulaire.

Si un graphe cubique est aux arêtes 3-colorables de manière unique, il a exactement trois cycles hamiltoniens, formés par les arêtes avec deux de ses trois couleurs, mais certains graphes cubiques avec seulement trois cycles hamiltoniens ne sont pas uniquement colorables à 3 arêtes^[5]. Tout graphe cubique planaire simple qui est uniquement 3-colorable aux arêtes contient un triangle^[1] mais W. T. Tutte (1972)^[6] a observé que le graphe de Petersen généralisé ${\displaystyle G(9,2)}$ qui est non planaire et sans triangle, est uniquement 3-colorable aux arêtes. Pendant de nombreuses années, il a été le seul graphe de ce type connu, et on l'avait supposé qu'il n'en avait pas d'autre, mais on connaît aujourd'hui une infinité de graphes cubiques non planaires, sans triangle et uniquement 3-colorables aux arêtes^[7].

Un graphe totalement colorable de manière unique est un graphe k-chromatique total qui n'a qu'une seule k-coloration totale possible, à une permutation des couleurs.

Les graphes chemins et les cycles de longueur divisible par 3 sont des graphes totalement colorables de manière unique. Mahmoodian & Shokrollahi^[8] ont émis l'hypothèse qu'ils sont également les seuls membres de cette famille.

Un graphe ${\displaystyle G}$ totalement colorable de façon unique avec ${\displaystyle k}$ couleurs et ${\displaystyle n}$ sommets a les propriétés suivantes :

1. ${\displaystyle \chi ''(G)=\Delta )(G)+1}$ sauf si ${\displaystyle G=K_{2}}$^[9]
2. ${\displaystyle \Delta )(G)\leq 2\delta (G)}$^[9]
3. ${\displaystyle \Delta (G)\leq n/2}$^[10]

où ${\displaystyle \chi ''(G)}$ est le nombre chromatique total, ${\displaystyle \Delta (G)}$ est le degré maximum, et ${\displaystyle \delta (G)}$ est le degré minimum de ${\displaystyle G}$.

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

• S. Akbari, « Two conjectures on uniquely totally colorable graphs », Discrete Mathematics, vol. 266, n^os 1–3,‎ 2003, p. 41–45 (DOI 10.1016/S0012-365X(02)00797-5 , MR 1991705).
• S. Akbari, M. Behzad, H. Hajiabolhassan et E. S. Mahmoodian, « Uniquely total colorable graphs », Graphs and Combinatorics, vol. 13, n^o 4,‎ 1997, p. 305–314 (DOI 10.1016/S0012-365X(02)00797-5 , MR 1485924).
• Sarah-Marie Belcastro et Ruth Haas, « Triangle-free uniquely 3-edge colorable cubic graphs », Contributions to Discrete Mathematics, vol. 10, n^o 2,‎ 2015, p. 39–44 (DOI 10.11575/cdm.v10i2.62320 , MR 3499076, arXiv 1508.06934).
• Béla Bollobás, Extremal Graph Theory, vol. 11, Academic Press, coll. « LMS Monographs », 1978 (MR 0506522).
• Thomas Fowler, Unique Coloring of Planar Graphs (Ph.D. thesis), Georgia Institute of Technology Mathematics Department, 1998 (lire en ligne).
• Christopher J. Hillar et Troels Windfeldt, « Algebraic characterization of uniquely vertex colorable graphs », Journal of Combinatorial Theory B, vol. 98, n^o 2,‎ 2008, p. 400–414 (DOI 10.1016/j.jctb.2007.08.004, MR 2389606, arXiv math/0606565, S2CID 108304).
• E. S. Mahmoodian, « Defining sets and uniqueness in graph colorings: a survey », Journal of Statistical Planning and Inference, vol. 73, n^os 1–2,‎ 1998, p. 85–89 (DOI 10.1016/S0378-3758(98)00053-6, MR 1655213).
• E. S. Mahmoodian et M. A. Shokrollahi, « Open problems at the combinatorics workshop of AIMC25 (Tehran, 1994) », dans Charles J. Colbourn, E. S. Mahmoodian (éditeurs), Combinatorics Advances, Kluwer Academic Publishers, coll. « Mathematics and its applications » (n^o 329), 1995, p. 321–324.
• Allen J. Schwenk, « Enumeration of Hamiltonian cycles in certain generalized Petersen graphs », Journal of Combinatorial Theory B, vol. 47, n^o 1,‎ 1989, p. 53–59 (DOI 10.1016/0095-8956(89)90064-6 , MR 1007713).
• Andrew G. Thomason, « Hamiltonian cycles and uniquely edge colourable graphs », Annals of Discrete Mathematics, vol. 3 « Advances in Graph Theory (Cambridge Combinatorial Conf., Trinity College, Cambridge, 1977) »,‎ 1978, p. 259–268 (MR 499124).
• Andrew G. Thomason, « Cubic graphs with three Hamiltonian cycles are not always uniquely edge colorable », Journal of Graph Theory, vol. 6, n^o 2,‎ 1982, p. 219–221 (DOI 10.1002/jgt.3190060218, MR 655209).
• M. Truszczyński, « Some results on uniquely colourable graphs », dans A. Hajnal, L. Lovász, Vera T. Sós (éditeurs), Finite and Infinite Sets. Proceedings of the sixth Hungarian combinatorial colloquium held in Eger, July 6–11, 1981, vol. 37, North-Holland, Amsterdam, coll. « Colloq. Math. Soc. János Bolyai », 1984 (MR 818274), p. 733–748.
• William T. Tutte, « Hamiltonian circuits », Atti dei Convegni Lincei, No. 17, Accad. Naz. Lincei, Rome « Colloquio Internazionale sulle Teorie Combinatorie (Rome, 1973), Tomo I »,‎ 1976, p. 193–199. (MR 0480185). cité par (belcastro et Haas 2015).
• Shao Ji Xu, « The size of uniquely colorable graphs », Journal of Combinatorial Theory B, vol. 50, n^o 2,‎ 1990, p. 319–320 (DOI 10.1016/0095-8956(90)90086-F , MR 1081235).
• R. J. Wilson, « Problem 2 », C. St. J. A. Nash-Williams, J.Sheehan (éds), Proc. British Comb. Conf. 1975, Winnipeg, Utilitas Math.,‎ 1976, p. 696. Cité par Thomason 1978.

• (en) Eric W. Weisstein, « Uniquely Colorable Graph », sur MathWorld

• Portail des mathématiques
• Portail de l'informatique théorique