#### 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