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[modifier | modifier le code]

Addario-Berry et al. (2008) 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^[1].

Complexité de reconnaissance[modifier | modifier le code]

Conforti et al. (2002b) ont donné le premier algorithme de reconnaissance en temps polynomial pour les graphes sans trous pairs, qui prend un temps en $O(n^{40})$ ^[2]. da Silva et Vušković (2013) améliorent l'estimation à $O(n^{19})$ . Chang et Lu (2012) puis Chang et Lu (2015) améliorent la borne et donnent $O(n^{11})$ time. Le meilleur algorithme connu en 2020 est par Lai, Lu et Thorup (2020) ; 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 Vušković (2010).

Notes[modifier | modifier le code]

↑ Maria Chudnovsky et Paul Seymour, « Even-hole-free graphs still have bisimplicial vertices », Arxiv,‎ 2019 (arXiv 1909.10967) (version révisée 2021)
↑ De fait, Conforti et al. 2002b présentent leur algorithme en affirmant qu'il s'exécute en temps polynomial, sans en donner une analyse explicite. Chudnovsky, Kawarabayashi et Seymour (2004) estiment qu'il prend un temps en « environ $O(n^{40})$ ».

Références[modifier | modifier le code]

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Even-hole-free graph » (voir la liste des auteurs).
Louigi Addario-Berry, Maria Chudnovsky, Frédéric Havet, Bruce Reed et Paul Seymour, « Bisimplicial vertices in even-hole-free graphs », Journal of Combinatorial Theory, Series B, vol. 98, n^o 6,‎ 2008, p. 1119–1164 (DOI 10.1016/j.jctb.2007.12.006 )
Dan Bienstock, « On the complexity of testing for odd holes and induced odd paths », Discrete Mathematics, vol. 90, n^o 1,‎ 1991, p. 85–92 (DOI 10.1016/0012-365X(91)90098-M )
Maria Chudnovsky, Ken-ichi Kawarabayashi et Paul Seymour, « Detecting even holes », Journal of Graph Theory, vol. 48, n^o 2,‎ 2004, p. 85–111 (DOI 10.1002/jgt.20040)
Michele Conforti, Gérard Cornuéjols, Ajai Kapoor et Kristina Vušković, « Even-hole-free graphs part I: Decomposition theorem », Journal of Graph Theory, vol. 39, n^o 1,‎ january 2002a, p. 6–49 (DOI 10.1002/jgt.10006, lire en ligne)
Michele Conforti, Gérard Cornuéjols, Ajai Kapoor et Kristina Vušković, « Even-hole-free graphs part II: Recognition algorithm », Journal of Graph Theory, vol. 40, n^o 4,‎ august 2002b, p. 238–266 (DOI 10.1002/jgt.10045, lire en ligne)
Murilo V.G. da Silva et Kristina Vušković, « Decomposition of even-hole-free graphs with star cutsets and 2-joins », Journal of Combinatorial Theory, Series B, vol. 103, n^o 1,‎ 2013, p. 144-183 (lire en ligne)
Hsien-Chih Chang et Hsueh-I Lu, « A Faster Algorithm to Recognize Even-Hole-Free Graphs », SODA '12: Proceedings of the Twenty-third Annual ACM-SIAM Symposium on Discrete Algorithms,‎ janvier 2012, p. 1286–1297 (ISBN 978-1-61197-210-8, DOI 10.1137/1.9781611973099.101 , lire en ligne)
Hsien-Chih Chang et Hsueh-I Lu, « A Faster Algorithm to Recognize Even-Hole-Free Graphs », Journal of Combinatorial Theory, Series B, vol. 113,‎ juillet 2015, p. 141–161 (DOI 10.1016/j.jctb.2015.02.001, arXiv 1311.0358, S2CID 1744497)
Kristina Vušković, « Even-hole-free graphs: a survey », Applicable Analysis and Discrete Mathematics, vol. 4, n^o 2,‎ 2010, p. 219–240 (DOI 10.2298/AADM100812027V, JSTOR 43666110, MR 2724633, lire en ligne)
Kai-Yuan Lai, Hsueh-I Lu et Mikkel Thorup, « Three-in-a-Tree in Near Linear Time », STOC 2020: Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing,‎ juin 2020, p. 1279–1292 (ISBN 9781450369794, DOI 10.1145/3357713, arXiv 1909.07446, lire en ligne)

Liens externes[modifier | modifier le code]

« Even-hole-free graphs », Information System on Graph Classes and their Inclusions, sur graphclasses.org

[1] Maria Chudnovsky et Paul Seymour, « Even-hole-free graphs still have bisimplicial vertices », Arxiv,‎ 2019 (arXiv 1909.10967) (version révisée 2021)

[2] De fait, Conforti et al. 2002b présentent leur algorithme en affirmant qu'il s'exécute en temps polynomial, sans en donner une analyse explicite. Chudnovsky, Kawarabayashi et Seymour (2004) estiment qu'il prend un temps en « environ $O(n^{40})$ ».

[1]

[2]