Alladi Ramakrishnan Hall
Detecting odd holes
Vaidy Sivaraman
University of Amsterdam, Amsterdam, The Netherlands
The The complexity of determining whether a graph has an induced odd
cycle of length at least 5 (odd hole) is unknown.
In this talk, I will
describe a polynomial-time algorithm to do this if the input graph does not
contain the bull (a particular 5-vertex graph that turns out to be important
in the theory of induced subgraphs) as an induced subgraph. This is joint
work with Maria Chudnovsky.
Done