Odd Hole Recognition in Graphs of Bounded Clique Size
journal contributionposted on 01.10.2009 by Michele Conforti, Gerard Cornuejols, Xinming Liu, Kristina Vušković, Giacomo Zambelli
Any type of content formally published in an academic journal, usually following a peer-review process.
In a graph G, an odd hole is an induced odd cycle of length at least five. A clique of G is a set of pairwise adjacent vertices. In this paper we consider the class Ck of graphs whose cliques have a size bounded by a constant k. Given a graph G in Ck, we show how to recognize in polynomial time whether G contains an odd hole.