Even-hole-free graphs part II: Recognition algorithm

DOI10.1002/jgt.10045zbMath1003.05095WikidataQ59904351 ScholiaQ59904351MaRDI QIDQ3150171

Cornuéjols, Gérard, Michele Conforti, Ajai Kapoor, Kristina Vušković

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

zbMATH Keywords

decomposition; polytime algorithm; even hole

Mathematics Subject Classification ID

05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

05C85: Graph algorithms (graph-theoretic aspects)

Related Items

Triangulated neighborhoods in even-hole-free graphs, Bisimplicial vertices in even-hole-free graphs, Even-hole-free graphs that do not contain diamonds: A structure theorem and its consequences, The strong perfect graph conjecture: 40 years of attempts, and its resolution, Decomposition of odd-hole-free graphs by double star cutsets and 2-joins, On the complexity of finding chordless paths in bipartite graphs and some interval operators in graphs and hypergraphs, Decomposing Berge graphs and detecting balanced skew partitions, A polynomial recognition algorithm for balanced matrices, Shortest Paths between Shortest Paths and Independent Sets, The Induced Disjoint Paths Problem

Cites Work

• Unnamed Item
• 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