Graphe trop plein

En théorie des graphes, un graphe trop plein est un graphe dont le nombre d'arêtes est supérieur au produit de son degré maximum et de la moitié de son nombre de sommets, c'est-à-dire

${\displaystyle |E|>\Delta (G)\lfloor |V|/2\rfloor }$

où ${\displaystyle |E|}$ est le nombre d'arêtes, ${\displaystyle \Delta (G)}$ est le degré maximum, et ${\displaystyle |V|}$ est le nombre de sommets de ${\displaystyle G}$. Un sous-graphe trop plein d'un graphe est un sous-graphe qui est trop plein. Une autre définition, plus forte, d'un sous-graphe trop plein ${\displaystyle S}$ d'un graphe ${\displaystyle G}$ demande qu'en plus ${\displaystyle \displaystyle \Delta (G)=\Delta (S)}$.

Un graphe cycle impair de longueur cinq ou plus est trop plein : en effet, le produit de son degré (égal à 2) par la moitié de sa longueur (arrondie à l'entier inférieur) est égal le nombre d'arêtes de ce cycle moins 1.

Plus généralement, un graphe régulier de degré ${\displaystyle \Delta }$ avec un nombre impair ${\displaystyle n}$ de sommets est trop plein, car son nombre d'arêtes qui est égal à ${\displaystyle (\Delta n)/2}$ est plus grand que ${\displaystyle \Delta \lfloor n/2\rfloor }$.

1. Les graphes trop pleins sont d'ordre impair.
2. Les graphes trop pleins sont de classe de coloration 2, c'est-à-dire toute coloration des arêtes nécessite au moins Δ + 1 couleurs.
3. Un graphe ${\displaystyle G}$ qui possède un sous-graphe trop plein ${\displaystyle S}$ et tel que ${\displaystyle \Delta (G)=\Delta (S)}$ est de classe 2.

En 1986, Amanda Chetwynd et Anthony Hilton ont formulé la conjecture suivante^[1] qui est maintenant connue sous le nom de conjecture du graphe trop plein :

Un graphe ${\displaystyle G}$ à ${\displaystyle n}$ sommets tel que ${\displaystyle \Delta (G)>n/3}$ est de classe 2 si et seulement s'il a un sous-graphe ${\displaystyle S}$ trop plein tel que ${\displaystyle \Delta (G)=\Delta (S)}$ .

Cette conjecture, si elle est vraie, a de nombreuses implications en théorie des graphes, et notamment la conjecture de 1-factorisation^[2].

Un graphe dans lequel ${\displaystyle \Delta \geq n/3}$ a au plus trois sous-graphes trop pleins induits, et on peut trouver un sous-graphe trop plein en temps polynomial. Quand ${\displaystyle \Delta \geq n/2}$, il y a au plus un sous-graphe induit trop plein, et on peut le trouver en temps linéaire^[3].

• Gary Chartrand et Ping Zhang, Chromatic graph theory, Chapman & Hall/CRC Press, coll. « Discrete mathematics and its applications », 2009 (ISBN 978-1-58488-800-0)
• Overfull graphs sur Google Scholar

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