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.