Graphe d'intervalle propre

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

Un graphe d'intervalle propre.

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

Propriétés

Une serre

Un graphe d'intervalle propre est nécessairement un graphe sans serre.

Démonstration

Soit G un graphe possédant une serre comme graphe induit. On appelle A,B,C,D les quatre sommets de la serre d'intervalles respectives I_a = [a₁;a₂],I_b = [b₁;b₂],Ic = [c₁;c₂] et I_d = [d₁;d₂] tels que le sommet D soit celui relié aux trois autres et que $a_1\le b_1\le c_1$.

Comme la serre 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 \not = \empty$ et $I_c \cap I_d \not = \empty$ 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 b2 \le c_1 \le d_2$, d'où $I_b \sub I_d$. G n'est donc pas un graphe d'intervalle propre.