Even and odd holes in cap-free graphs

DOI<289::AID-JGT4>3.0.CO;2-3 10.1002/(SICI)1097-0118(199904)30:4<289::AID-JGT4>3.0.CO;2-3zbMath0920.05028OpenAlexW4252569207MaRDI QIDQ4238043

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

Publication date: 26 May 1999

Full work available at URL: https://doi.org/10.1002/(sici)1097-0118(199904)30:4<289::aid-jgt4>3.0.co;2-3

zbMATH Keywords

capdecompositiontestingstrong perfect graph conjectureMeyniel graphsodd holeschordless cycle\(\beta\)-perfect graphscap-free graphseven-signable and odd-signable graphspolynomial recognition algorithms

Mathematics Subject Classification ID

Structural characterization of families of graphs (05C75) Coloring of graphs and hypergraphs (05C15) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Negative (and positive) circles in signed graphs: a problem collection ⋮ 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 ⋮ Solving the clique cover problem on (bull, \(C_4\))-free graphs ⋮ Structure and algorithms for (cap, even hole)-free graphs ⋮ Amalgams and χ-Boundedness ⋮ Graphs of separability at most 2 ⋮ Graphs without odd holes, parachutes or proper wheels: A generalization of Meyniel graphs and of line graphs of bipartite graphs ⋮ Decomposition techniques applied to the clique-stable set separation problem ⋮ On the forbidden induced subgraph sandwich problem ⋮ A note on chromatic number of (cap, even hole)-free graphs ⋮ Unnamed Item ⋮ Polynomial \(\chi \)-binding functions and forbidden induced subgraphs: a survey ⋮ Graphs of Separability at Most Two: Structural Characterizations and Their Consequences ⋮ A better upper bound on the chromatic number of (cap, even-hole)-free graphs ⋮ Erdős-Hajnal for cap-free graphs ⋮ Even-hole-free graphs part I: Decomposition theorem ⋮ A structure theorem for graphs with no cycle with a unique chord and its consequences ⋮ Recognition of quasi-Meyniel graphs ⋮ Two classes of \(\beta \)-perfect graphs that do not necessarily have simplicial extremes ⋮ 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 ⋮ Unnamed Item ⋮ A faster algorithm to recognize even-hole-free graphs ⋮ Even-hole-free graphs part II: Recognition algorithm