Abstract: The complexity of testing whether a graph contains an induced odd cycle of length at least five is currently unknown. In this paper we show that this can be done in polynomial time if the input graph has no induced subgraph isomorphic to the bull (a triangle with two disjoint pendant edges).
Recommendations
Cites work
Cited in
(11)- On the complexity of testing for odd holes and induced odd paths
- On graphs with 2 trivial distance ideals
- Distance ideals of graphs
- Finding Large H-Colorable Subgraphs in Hereditary Graph Classes
- Odd Hole Recognition in Graphs of Bounded Clique Size
- scientific article; zbMATH DE number 7651174 (Why is no real title available?)
- Blazing a trail via matrix multiplications: a faster algorithm for non-shortest induced paths
- Structure and coloring of (P₇, C₅, diamond)-free graphs
- Improved algorithms for perfect graphs and odd holes
- Graphs with two trivial distance ideals over the ring of polynomials with integer coefficients
- The structure of bull-free graphs I -- three-edge-paths with centers and anticenters
This page was built for publication: Odd holes in bull-free graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4638616)
