Abstract:
Un résultat classique (Golumbic et Goss) affirme que tout graphe biparti sans trou de longueur au moins 6 possède une arête bi-simpliciale. Ce résultat admet des formulations équivalentes concernant les matrices totalement équilibrées (Hoffman, Kolen, Sakarovitch) ou les graphes fortement triangulés (Farber). Nous démontrons une généralisation sous la forme du théorème suivant: dans tout graphe qui ne contient pas de "taureau" ni de trou de longueur au moins 5, il existe un sommet qui n'est pas le milieu d'un P5. Le but original de ce résultat est en fait de considérer les graphes parfaits sans taureau et sans antitrou de longueur au moins 5, et de leur appliquer un algorithme de coloration de sommets par contraction séquentiel. Un corollaire du théorème ci-dessus est qu'un tel algorithme fonctionne de manière optimale. Sa complexité est meilleure que ce qui était connu jusqu'ici.