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

Exemples

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

Propriétés

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.

Conjecture du graphe trop plein

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].

Algorithmes

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].

Références

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

1. Amanda G. Chetwynd et Anthony J. W. Hilton, « Star multigraphs with three vertices of maximum degree », Mathematical Proceedings of the Cambridge Philosophical Society, vol. 100, n^o 2,‎ 1986, p. 303–317 (DOI 10.1017/S030500410006610X, MR 848854, lire en ligne).
2. Amanda G. Chetwynd et Anthony J. W. Hilton, « 1-factorizing regular graphs of high degree—an improved bound », Discrete Mathematics, vol. 75, n^os 1–3,‎ 1989, p. 103–112 (DOI 10.1016/0012-365X(89)90082-4 , MR 1001390).
3. Thomas Niessen, « How to find overfull subgraphs in graphs with large maximum degree. II », Electronic Journal of Combinatorics, vol. 8, n^o 1,‎ 2001, article n^o R7 (11 p.) (MR 1814514, lire en ligne).

Bibliographie

• 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