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.

Propriétés

Modèle:Harvsp 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.

Complexité de reconnaissance

Modèle:Harvsp ont donné le premier algorithme de reconnaissance en temps polynomial pour les graphes sans trous pairs, qui prend un temps en $O(n^{40})$. Modèle:Harvsp améliorent l'estimation à $O(n^{19})$. Modèle:Harvsp puis Modèle:Harvsp améliorent la borne et donnent $O(n^{11})$ time. Le meilleur algorithme connu en 2020 est par Modèle:Harvsp ; il est en temps $O(n^9)$.

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 Modèle:Harvsp.

Références

• Modèle:Article
• Modèle:Article
• Modèle:Article
• Modèle:Article
• Modèle:Article
• Modèle:Article
• Modèle:Article
• Modèle:Article
• Modèle:Article
• Modèle:Article

Liens externes

• Modèle:Lien web