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
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.
| Item Type | Article |
|---|---|
| Copyright holders | © 2006 by the Society for Industrial and Applied Mathematics, Philadelphia, PA. |
| Keywords | odd hole, recognition algorithm, cleaning, decomposition |
| Departments | Management |
| DOI | 10.1137/S089548010444540X |
| Date Deposited | 25 Jan 2011 16:06 |
| URI | https://researchonline.lse.ac.uk/id/eprint/31700 |