Finding minimum clique capacity

Research output: Contribution to journalArticle

Abstract

Let C be a clique of a graph G. The capacity of C is defined to be ({pipe}V (G)/C{pipe}+{pipe}D{pipe})/2, where D is the set of vertices in V (G)/C that have both a neighbour and a non-neighbour in C. We give a polynomial-time algorithm to find the minimum clique capacity in a graph G. This problem arose in the study [1] of packing vertex-disjoint induced three-vertex paths in a graph with no stable set of size three, which in turn was motivated by Hadwiger's conjecture.

Original languageEnglish (US)
Pages (from-to)283-287
Number of pages5
JournalCombinatorica
Volume32
Issue number3
DOIs
StatePublished - Apr 1 2012

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics
  • Computational Mathematics

Fingerprint Dive into the research topics of 'Finding minimum clique capacity'. Together they form a unique fingerprint.

Cite this