Even-hole-free graphs part II: Recognition algorithm
From MaRDI portal
Publication:3150171
DOI10.1002/jgt.10045zbMath1003.05095OpenAlexW2528399963WikidataQ59904351 ScholiaQ59904351MaRDI QIDQ3150171
Kristina Vušković, Cornuéjols, Gérard, Ajai Kapoor, Michele Conforti
Publication date: 29 September 2002
Published in: Journal of Graph Theory (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1002/jgt.10045
Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items
Coloring graphs with no even hole \(\geqslant 6\): the triangle-free case, One-three join: a graph operation and its consequences, Detecting 2-joins faster, Detecting a long even hole, Triangulated neighborhoods in even-hole-free graphs, Induced subgraphs and tree decompositions. I: Even-hole-free graphs of bounded degree, A note on coloring \((4K_1, C_4, C_6)\)-free graphs with a \(C_7\), Structure and algorithms for (cap, even hole)-free graphs, Finding a shortest even hole in polynomial time, On the structure and clique‐width of (4K1,C4,C6,C7)‐free graphs, The Induced Disjoint Paths Problem, Coloring \((4K_1,C_4,C_6)\)-free graphs, On the structure of (pan, even hole)‐free graphs, Complexity of independent set reconfigurability problems, On the forbidden induced subgraph sandwich problem, Algorithms for finding an induced cycle in planar graphs, Shortest Paths between Shortest Paths and Independent Sets, Decomposing Berge graphs and detecting balanced skew partitions, Bisimplicial vertices in even-hole-free graphs, On the structure of (even hole, kite)-free graphs, On the complexity of finding chordless paths in bipartite graphs and some interval operators in graphs and hypergraphs, Some completion problems for graphs without chordless cycles of prescribed lengths, Polyhedral properties of the induced cluster subgraphs, The sandwich problem for decompositions and almost monotone properties, Stable sets and graphs with no even holes, Separation Choosability and Dense Bipartite Induced Subgraphs, Even-hole-free graphs that do not contain diamonds: A structure theorem and its consequences, Induced packing of odd cycles in planar graphs, Combinatorial optimization with 2-joins, Decomposition of odd-hole-free graphs by double star cutsets and 2-joins, A polynomial recognition algorithm for balanced matrices, The strong perfect graph conjecture: 40 years of attempts, and its resolution, Unnamed Item, A faster algorithm to recognize even-hole-free graphs
Cites Work
- Star-cutsets and perfect graphs
- On the complexity of testing for odd holes and induced odd paths
- Decomposition of balanced matrices
- Balanced \(0,\pm 1\) matrices. I: Decomposition
- \(\beta\)-perfect graphs
- Compositions for perfect graphs
- Even-hole-free graphs part I: Decomposition theorem
- Even and odd holes in cap-free graphs
