# Resource title

Odd hole recognition in graphs of bounded clique size

# Resource description

In a graph $G$, an odd hole is an induced odd cycle of length at least 5. A clique of $G$ is a set of pairwise adjacent vertices. In this paper we consider the class ${\cal C}_k$ of graphs whose cliques have a size bounded by a constant $k$. Given a graph $G$ in ${\cal C}_k$, we show how to recognize in polynomial time whether $G$ contains an odd hole.

en

# Resource resource URL

http://eprints.lse.ac.uk/31700/