Odd hole recognition in graphs of bounded clique size
Conforti, M., Cornuéjols, G., Liu, X., Vuskovic, K. & Zambelli, G.
(2006).
Odd hole recognition in graphs of bounded clique size.
SIAM Journal on Discrete Mathematics,
20(1), 42-48.
https://doi.org/10.1137/S089548010444540X
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. |
| Departments | LSE > Academic Departments > Management |
| DOI | 10.1137/S089548010444540X |
| Date Deposited | 25 Jan 2011 |
| URI | https://researchonline.lse.ac.uk/id/eprint/31700 |
Explore Further
- https://www.scopus.com/pages/publications/33847656737 (Scopus publication)
- http://www.siam.org/journals/sidma.php (Official URL)