Graphe à coloration unique

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}$.