Accession Number:

AD1021245

Title:

Odd Hole Recognition in Graphs of Bounded Clique Size

Descriptive Note:

Journal Article - Open Access

Corporate Author:

Carnegie Mellon University Pittsburgh United States

Report Date:

2005-08-23

Pagination or Media Count:

10.0

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.

Subject Categories:

  • Statistics and Probability

Distribution Statement:

APPROVED FOR PUBLIC RELEASE