Even-hole-free graphs part I: Decomposition theorem
From MaRDI portal
Publication:2778281
DOI10.1002/jgt.10006zbMath1005.05034OpenAlexW2528053456WikidataQ59904365 ScholiaQ59904365MaRDI QIDQ2778281
Kristina Vušković, Michele Conforti, Cornuéjols, Gérard, Ajai Kapoor
Publication date: 2 June 2002
Published in: Journal of Graph Theory (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1002/jgt.10006
Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Perfect graphs (05C17)
Related Items
Coloring graphs with no even hole \(\geqslant 6\): the triangle-free case, 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, Hereditary Efficiently Dominatable Graphs, The (theta, wheel)-free graphs. I: Only-prism and only-pyramid graphs, The (theta, wheel)-free graphs. II: Structure theorem, Reconfiguration of Vertex Covers in a Graph, A note on coloring \((4K_1, C_4, C_6)\)-free graphs with a \(C_7\), Even-hole-free graphs still have bisimplicial vertices, Finding a shortest even hole in polynomial time, On the structure and clique‐width of (4K1,C4,C6,C7)‐free graphs, Automated conjecturing. III. Property-relations conjectures, Even-hole-free planar graphs have bounded treewidth, The Induced Disjoint Paths Problem, Coloring \((4K_1,C_4,C_6)\)-free graphs, Graphs of separability at most 2, Complexity of independent set reconfigurability problems, Square-free perfect graphs., Algorithms for finding an induced cycle in planar graphs, Graphs of Separability at Most Two: Structural Characterizations and Their Consequences, 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, Vertex elimination orderings for hereditary graph classes, Stable sets and graphs with no even holes, 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, Even-hole-free graphs part II: Recognition algorithm
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Star-cutsets and perfect graphs
- Alpha-balanced graphs and matrices and GF(3)-representability of matroids
- On the complexity of testing for odd holes and induced odd paths
- Decomposition of balanced matrices
- A theorem of Truemper
- Balanced \(0,\pm 1\) matrices. I: Decomposition
- \(\beta\)-perfect graphs
- Compositions for perfect graphs
- Even and odd holes in cap-free graphs
