Graphe d'intervalles propre

Un graphe d'intervalles propre est un graphe d'intervalles possédant une représentation d'intervalles dans laquelle aucun intervalle n'est inclus dans l'autre.

Un graphe d'intervalle qui n'est pas un graphe d'intervalle propre.

Un graphe d'intervalle propre.

Propriétés

Une griffe

Un graphe d'intervalles propre est nécessairement un graphe sans griffe.

Démonstration

Soit $G$ un graphe possédant une griffe comme sous-graphe induit. On appelle $A,B,C,D$ les quatre sommets de la griffe d'intervalles respectives $I_{a}=[a_{1};a_{2}]$,$I_{b}=[b_{1};b_{2}]$,$Ic=[c_{1};c_{2}]$ et $I_{d}=[d_{1};d_{2}]$ tels que le sommet $D$ soit celui relié aux trois autres et que $a_{1}\leq b_{1}\leq c_{1}$.

Comme la griffe est un graphe induit, $A$, $B$ et $C$ ne sont pas voisins dans $G$. On a donc $a_{1}\leq a_{2}\leq b_{1}\leq b_{2}\leq c_{1}\leq c_{2}$.

$D$ est voisin de $A$ et $C$ donc $I_{a}\cap I_{d}\not =\emptyset$ et $I_{c}\cap I_{d}\not =\emptyset$ d'où $d_{1}\leq a_{2}$ et $c_{1}\leq d_{2}$. On a donc $d_{1}\leq a_{2}\leq b_{1}\leq b2\leq c_{1}\leq d_{2}$, d'où $I_{b}\subset I_{d}$. $G$ n'est donc pas un graphe d'intervalle propre.