Even-hole-free graphs: A survey
From MaRDI portal
Publication:4899861
DOI10.2298/AADM100812027VzbMath1265.05518WikidataQ59903197 ScholiaQ59903197MaRDI QIDQ4899861
Publication date: 10 January 2013
Published in: Applicable Analysis and Discrete Mathematics (Search for Journal in Brave)
combinatorial optimizationperfect graphsstrong perfect graph conjectureeven-hole-free graphspolynomial time recognition
Research exposition (monographs, survey articles) pertaining to combinatorics (05-02) Structural characterization of families of graphs (05C75) Graph algorithms (graph-theoretic aspects) (05C85) Perfect graphs (05C17)
Related Items (21)
Negative (and positive) circles in signed graphs: a problem collection ⋮ Induced subgraphs and tree decompositions. I: Even-hole-free graphs of bounded degree ⋮ Forbidden induced subgraphs ⋮ Even-hole-free graphs still have bisimplicial vertices ⋮ Structure and algorithms for (cap, even hole)-free graphs ⋮ Finding a shortest even hole in polynomial time ⋮ (Theta, triangle)‐free and (even hole, K4)‐free graphs—Part 1: Layered wheels ⋮ Clique separator decomposition of hole-free and diamond-free graphs and algorithmic consequences ⋮ On the connectivity and diameter of geodetic graphs ⋮ On the structure of (pan, even hole)‐free graphs ⋮ A note on chromatic number of (cap, even hole)-free graphs ⋮ Polynomial \(\chi \)-binding functions and forbidden induced subgraphs: a survey ⋮ On the tree-width of even-hole-free graphs ⋮ A better upper bound on the chromatic number of (cap, even-hole)-free graphs ⋮ Vertex elimination orderings for hereditary graph classes ⋮ Independent Set Reconfiguration in Cographs and their Generalizations ⋮ Open Problems on Graph Coloring for Special Graph Classes ⋮ Counting Perfect Matchings and the Switch Chain ⋮ Efficiently decomposing, recognizing and triangulating hole-free graphs without diamonds ⋮ Unnamed Item ⋮ A faster algorithm to recognize even-hole-free graphs
This page was built for publication: Even-hole-free graphs: A survey
