article

Odd Hole Recognition in Graphs of Bounded Clique Size

Authors:

Giacomo ZambelliAuthors Info & Claims

SIAM Journal on Discrete Mathematics, Volume 20, Issue 1

Pages 42 - 48

https://doi.org/10.1137/S089548010444540X

Published: 01 January 2006 Publication History

Abstract

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.

Cited By

View all

Lai KLu HThorup MMakarychev KMakarychev YTulsiani MKamath GChuzhoy J(2020)Three-in-a-tree in near linear timeProceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing10.1145/3357713.3384235(1279-1292)Online publication date: 22-Jun-2020
https://dl.acm.org/doi/10.1145/3357713.3384235
Kuo YLeung J(2016)On the mixed set covering, packing and partitioning polytopeDiscrete Optimization10.1016/j.disopt.2016.05.00422:PA(162-182)Online publication date: 1-Nov-2016
https://dl.acm.org/doi/10.1016/j.disopt.2016.05.004
Chang HLu H(2015)A faster algorithm to recognize even-hole-free graphsJournal of Combinatorial Theory Series B10.1016/j.jctb.2015.02.001113:C(141-161)Online publication date: 1-Jul-2015
https://dl.acm.org/doi/10.1016/j.jctb.2015.02.001
Show More Cited By

Index Terms

Odd Hole Recognition in Graphs of Bounded Clique Size
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
  2. Mathematical analysis
    1. Numerical analysis
      1. Computations on polynomials
2. Theory of computation
  1. Randomness, geometry and discrete structures

Recommendations

Graphs without odd holes, parachutes or proper wheels: a generalization of Meyniel graphs and of line graphs of bipartite graphs

We prove that the strong perfect graph conjecture holds for graphs that do not contain parachutes or proper wheels. This is done by showing the following theorem: If a graph G contains no odd hole, no parachute and no proper wheel, then G is bipartite ...
Disjoint clique cutsets in graphs without long holes

A biclique cutset is a cutset that induces the disjoint union of two cliques. A hole is an induced cycle with at least five vertices. A graph is biclique separable if it has no holes and each induced subgraph that is not a clique contains a clique ...
Decomposition of even-hole-free graphs with star cutsets and 2-joins

In this paper we consider the class of simple graphs defined by excluding, as induced subgraphs, even holes (i.e. chordless cycles of even length). These graphs are known as even-hole-free graphs. We prove a decomposition theorem for even-hole-free ...

Comments

Information & Contributors

Information

Published In

cover image SIAM Journal on Discrete Mathematics

SIAM Journal on Discrete Mathematics Volume 20, Issue 1

2006

271 pages

ISSN:0895-4801

Issue’s Table of Contents

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 01 January 2006

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 22 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Lai KLu HThorup MMakarychev KMakarychev YTulsiani MKamath GChuzhoy J(2020)Three-in-a-tree in near linear timeProceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing10.1145/3357713.3384235(1279-1292)Online publication date: 22-Jun-2020
https://dl.acm.org/doi/10.1145/3357713.3384235
Kuo YLeung J(2016)On the mixed set covering, packing and partitioning polytopeDiscrete Optimization10.1016/j.disopt.2016.05.00422:PA(162-182)Online publication date: 1-Nov-2016
https://dl.acm.org/doi/10.1016/j.disopt.2016.05.004
Chang HLu H(2015)A faster algorithm to recognize even-hole-free graphsJournal of Combinatorial Theory Series B10.1016/j.jctb.2015.02.001113:C(141-161)Online publication date: 1-Jul-2015
https://dl.acm.org/doi/10.1016/j.jctb.2015.02.001
Brandstädt AMosca R(2015)Maximum Weight Independent Sets in Odd-Hole-Free Graphs Without Dart or Without BullGraphs and Combinatorics10.1007/s00373-014-1461-x31:5(1249-1262)Online publication date: 1-Sep-2015
https://dl.acm.org/doi/10.1007/s00373-014-1461-x
Chang HLu H(2012)A faster algorithm to recognize even-hole-free graphsProceedings of the twenty-third annual ACM-SIAM symposium on Discrete algorithms10.5555/2095116.2095217(1286-1297)Online publication date: 17-Jan-2012
https://dl.acm.org/doi/10.5555/2095116.2095217
Roussel FRusu IThuillier H(2009)The Strong Perfect Graph ConjectureDiscrete Mathematics10.1016/j.disc.2009.05.024309:20(6092-6113)Online publication date: 1-Oct-2009
https://dl.acm.org/doi/10.1016/j.disc.2009.05.024
Golovach PKamiński MPaulusma DThilikos D(2009)Induced Packing of Odd Cycles in a Planar GraphProceedings of the 20th International Symposium on Algorithms and Computation10.1007/978-3-642-10631-6_53(514-523)Online publication date: 5-Dec-2009
https://dl.acm.org/doi/10.1007/978-3-642-10631-6_53

View Options

View options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Abstract

Cited By

Index Terms

Recommendations

Graphs without odd holes, parachutes or proper wheels: a generalization of Meyniel graphs and of line graphs of bipartite graphs

Disjoint clique cutsets in graphs without long holes

Decomposition of even-hole-free graphs with star cutsets and 2-joins

Comments

Information

Published In

Publisher

Publication History

Author Tags

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Get Access

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations