Odd Hole Recognition in Graphs of Bounded Clique Size
2009-10-01T00:00:00Z (GMT) by
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 C<sub>k</sub> of graphs whose cliques have a size bounded by a constant k. Given a graph G in C<sub>k</sub>, we show how to recognize in polynomial time whether G contains an odd hole.