Odd Hole Recognition in Graphs of Bounded Clique Size.pdf.pdf' (142.8 kB)
Download file

Odd Hole Recognition in Graphs of Bounded Clique Size

Download (142.8 kB)
journal contribution
posted on 01.10.2009, 00:00 by Michele Conforti, Gerard CornuejolsGerard Cornuejols, Xinming Liu, Kristina Vušković, Giacomo Zambelli
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.

History

Date

01/10/2009

Usage metrics

Exports