Odd hole recognition in graphs of bounded clique size

Conforti, Michele; Cornuéjols, Gérard; Liu, Xinming; Vuskovic, Kristina; and Zambelli, Giacomo (2006) Odd hole recognition in graphs of bounded clique size SIAM Journal on Discrete Mathematics, 20 (1). pp. 42-48. ISSN 0895-4801
Copy

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.

Full text not available from this repository.

Atom BibTeX OpenURL ContextObject in Span OpenURL ContextObject Dublin Core MPEG-21 DIDL Data Cite XML EndNote HTML Citation METS MODS RIOXX2 XML Reference Manager Refer ASCII Citation
Export

Downloads