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
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
