Graphe d'intervalles propre

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 b2\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