Graphe d'intervalles propre

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

Un graphe d'intervalle 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.

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\le b_1\le c_1$.

Comme la griffe est un graphe induit, $A$, $B$ et $C$ ne sont pas voisins dans $G$. On a donc $a_1\le a_2\le b_1\le b_2\le c_1\le c_2$.

$D$ est voisin de $A$ et $C$ donc $I_a\cap I_d=\mathrm{\varnothing }$ et $I_c\cap I_d=\mathrm{\varnothing }$ d'où $d_1\le a_2$ et $c_1\le d_2$. On a donc $d_1\le a_2\le b_1\le b_2\le c_1\le d_2$, d'où $I_b\subset I_d$. $G$ n'est donc pas un graphe d'intervalle propre.