Odd Hole Recognition in Graphs of Bounded Clique Size

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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Aug 23, 2005
Accession Number
AD1021245

Entities

People

  • Giacomo Zambelli
  • Gérard Cornuéjols
  • Kristina Vušković
  • Michele Conforti
  • Xinming Liu

Organizations

  • Carnegie Mellon University

Tags

DTIC Thesaurus Topics

  • Abstracts
  • Algorithms
  • Commerce
  • Decomposition
  • Heuristic Methods
  • Iterations
  • Mathematics
  • Notation
  • Optimization
  • Polynomials
  • Recognition
  • Schools
  • Sequences
  • Specifications
  • Universities

Fields of Study

  • Mathematics

Readers

  • Graph Algorithms and Convex Optimization.