Even and odd holes in cap-free graphs
DOI10.1002/(SICI)1097-0118(199904)30:4%3C289::AID-JGT4%3E3.0.CO;2-3zbMATH Open0920.05028OpenAlexW4252569207MaRDI QIDQ4238043FDOQ4238043
Gérard Cornuéjols, 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%3C289::aid-jgt4%3E3.0.co;2-3
Recommendations
decompositiontestingcapodd holesMeyniel graphschordless cyclestrong perfect graph conjecture\(\beta\)-perfect graphscap-free graphseven-signable and odd-signable graphspolynomial recognition algorithms
Graph algorithms (graph-theoretic aspects) (05C85) Coloring of graphs and hypergraphs (05C15) Structural characterization of families of graphs (05C75) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)
Cited In (32)
- Even-hole-free graphs: A survey
- The (theta, wheel)-free graphs. I: Only-prism and only-pyramid graphs
- Recognition of quasi-Meyniel graphs
- Graphs of separability at most 2
- Even-hole-free graphs that do not contain diamonds: A structure theorem and its consequences
- Structure and algorithms for (cap, even hole)-free graphs
- Polynomial \(\chi \)-binding functions and forbidden induced subgraphs: a survey
- Triangulated neighborhoods in even-hole-free graphs
- Solving the clique cover problem on (bull, \(C_4\))-free graphs
- Title not available (Why is that?)
- Negative (and positive) circles in signed graphs: a problem collection
- Graphs without odd holes, parachutes or proper wheels: A generalization of Meyniel graphs and of line graphs of bipartite graphs
- Hereditary Efficiently Dominatable Graphs
- Two classes of \(\beta \)-perfect graphs that do not necessarily have simplicial extremes
- Amalgams and χ-Boundedness
- A structure theorem for graphs with no cycle with a unique chord and its consequences
- Stable sets and graphs with no even holes
- Detecting even holes
- Blazing a trail via matrix multiplications: a faster algorithm for non-shortest induced paths
- Induced subgraphs and tree decompositions. I: Even-hole-free graphs of bounded degree
- Even-hole-free graphs. I: Decomposition theorem
- Odd Hole Recognition in Graphs of Bounded Clique Size
- On the forbidden induced subgraph sandwich problem
- Graphs of Separability at Most Two: Structural Characterizations and Their Consequences
- Erdős-Hajnal for cap-free graphs
- A faster algorithm to recognize even-hole-free graphs
- Decomposition techniques applied to the clique-stable set separation problem
- A note on chromatic number of (cap, even hole)-free graphs
- Title not available (Why is that?)
- A better upper bound on the chromatic number of (cap, even-hole)-free graphs
- Even-hole-free graphs part II: Recognition algorithm
- Vertex elimination orderings for hereditary graph classes
This page was built for publication: Even and odd holes in cap-free graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4238043)
