webcal

Description

Combinatorics Seminar

Speaker: Vaidy Sivaraman (University of Central Florida)
Venue: Ramanujan Hall
Date & Time: Monday 13th August, 4-5 PM.

Title: Detecting odd holes
Abstract: 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.