Odd holes in bull-free graphs
classification
🧮 math.CO
cs.DM
keywords
graphinducedbullbull-freecomplexitycontainscurrentlycycle
read the original 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).
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.