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'intervalles propre est nécessairement un graphe sans griffe.

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

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

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

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