Jämn-hål-fri graf

Inom det matematiska området för grafteorin är en graf fri från jämna hål om den inte innehåller någon inducerad cykel med ett jämnt antal hörn .

Addario-Berry et al. (2008) visade att varje graf utan jämna hål innehåller en bisimpliciell vertex, vilket avgjorde en gissning av Reed.

Erkännande

Conforti et al. (2002b) gav den första polynomtidsigenkänningsalgoritmen för grafer utan jämna hål, som körs i ${\mathcal {O}}(n^{40})$ tid. da Silva & Vušković (2008) förbättrade senare detta till ${\mathcal {O}}(n^{19})$ . Chang & Lu (2012) och Chang & Lu (2015) förbättrade detta till ${\mathcal {O}}(n^{11})$ tid. Den för närvarande mest kända algoritmen ges av Lai, Lu & Thorup (2020) som körs i ${\mathcal {O}}(n^{9})$ tid.

Även om grafer utan jämna hål kan kännas igen i polynomtid, är det NP -komplett för att avgöra om en graf innehåller ett jämnt hål som inkluderar en specifik vertex.

Det är okänt om graffärgning och det maximala oberoende uppsättningsproblemet kan lösas i polynomtid på grafer utan jämna hål, eller om de är NP-kompletta. Den maximala klicken kan dock hittas i grafer utan jämna hål i polynomtid.

Anteckningar

• Addario-Berry, Louigi; Chudnovsky, Maria ; Havet, Frédéric; Reed, Bruce ; Seymour, Paul (2008), "Bisimplicial vertices in even-hole-free graphs", Journal of Combinatorial Theory , Series B, 98 (6): 1119–1164, doi : 10.1016/j.jctb.2007.12.006
• Bienstock, Dan (1991), "Om komplexiteten i att testa för udda hål och inducerade udda banor", Discrete Mathematics , 90 (1): 85–92, doi : 10.1016/0012-365X(91)90098-M
• Chudnovsky, Maria ; Kawarabayashi, Ken-ichi ; Seymour, Paul (2004), "Detecting even holes", Journal of Graph Theory , 48 (2): 85–111, doi : 10.1002/jgt.20040
• Conforti, Michele; Cornuéjols, Gérard ; Kapoor, Ajai; Vušković, Kristina (januari 2002a), "Even-hole-free graphs part I: Decomposition theorem" (PDF) , Journal of Graph Theory , 39 (1): 6–49, doi : 10.1002/jgt.10006
• Conforti, Michele; Cornuéjols, Gérard ; Kapoor, Ajai; Vušković, Kristina (augusti 2002b), "Even-hole-free graphs part II: Recognition algorithm" (PDF) , Journal of Graph Theory , 40 (4): 238–266, doi : 10.1002/jgt.10045
• da Silva, Murilo VG; Vušković, Kristina (2008), Nedbrytning av grafer utan jämna hål med stjärnsnitt och 2-skarvar
•   Chang, Hsien-Chih; Lu, Hsueh-I (januari 2012), " A Faster Algorithm to Recognize Even-Hole-Free Graphs" , SODA '12: Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms : 1286–1297, do 1297 , do . /1.9781611973099.101 , ISBN 978-1-61197-210-8
•   Chang, Hsien-Chih; Lu, Hsueh-I (juli 2015), "A Faster Algorithm to Recognize Even-Hole-Free Graphs", Journal of Combinatorial Theory, Series B , 113 : 141–161, arXiv : 1311.0358 , doi : 101/10. 2015.02.001 , S2CID 1744497
•   Vušković, Kristina (2010), "Even-hole-free graphs: a survey" (PDF) , Applicable Analysis and Discrete Mathematics , 4 ( 2): 219–240, doi : 10.2298/AADM100812027V , 6MR 12026 , 6MR 12026 , 6MR 12026 , 6  
•   Lai, Kai-Yuan; Lu, Hsueh-I; Thorup, Mikkel (juni 2020), "Three-in-a-Tree in Near Linear Time" , STOC 2020 : Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing : 1279–1292, arXiv : 1909 : 410/51 , 4909/51 . 3357713 , ISBN 9781450369794

externa länkar

• "Jämna hålfria grafer" , informationssystem om grafklasser och deras inkludering