Odd Hole Recognition in Graphs of Bounded Clique Size

reportActive / Technical Report | Accession Number: AD1021245 | Open PDF

Abstract:

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.

Author(s):
Conforti, Michele ; Cornuejols, Gerard ; Liu, Xinming ; Vuskovic, Kristina ; Zambelli, Giacomo
Author Organization(s):
Carnegie Mellon University Pittsburgh United States
Descriptive Note:
Journal Article - Open Access
Supplementary Note:
SIAM Journal on Discrete Mathematics , 20, 1, 01 Jan 0001, 01 Jan 0001,
Pagination:
0010

Security Markings

DOCUMENT & CONTEXTUAL SUMMARY

Distribution:
Approved For Public Release
Distribution Statement:
Approved For Public Release;

RECORD

Collection: TR
Subject Terms
Joint Capability Areas:
JCA_1.2_Force Preparation; JCA_1_Force Support; JCA_1.2.3_Educating
Communities of Interest:
No COI(s) Identified
Descriptor(s):
polynomials, algorithms, mathematical analysis, DECOMPOSITION, cleaning, GRAPHS
Field(s)/Group(s):
Statistics and Probability
Keyword(s):
odd hole, recognition algorithm
Report Date:
2005 Aug 23
Creation Date:
2005 Aug 23