Graphe sans trou pair

En théorie des graphes, un graphe est sans trou pair s'il ne contient pas de cycle induit avec un nombre pair de sommets. ont démontré qu'un graphe sans trou pair contient un sommet bisimplicial (un sommet dont le voisinage peut être partitionné en au plus 2 cliques), et résolvent ainsi un conjecture de Reed. En fait, la démonstration donnée dans cet article est incorrecte : Maria Chudnovsky et Paul Seymour annoncent en 2019 une nouvelle démonstration. ont donné le premier algorithme de reconnaissance en temps polynomial pour les graphes sans trous pairs, qui prend un temps en . améliorent l'estimation à . puis améliorent la borne et donnent time. Le meilleur algorithme connu en 2020 est par ; il est en temps . Alors que les graphes sans trou pair peuvent être reconnus en temps polynomial, il est NP-complet de déterminer si un graphe contient un trou pair qui passe par un sommet spécifique. On ne sait pas si la coloration de graphe et le problème du stable maximal peuvent être résolus en temps polynomial dans des graphes sans trous pairs, ou s'ils sont NP-complets. Cependant, la clique maximale peut être trouvée dans les graphes sans trous pairs en temps polynomial comme montré par .