Skip to main content

Finding minimum clique capacity

Author(s): Chudnovsky, Maria; Oum, Sang-Il; Seymour, Paul D

Download
To refer to this page use: http://arks.princeton.edu/ark:/88435/pr1d107
Abstract: Let C be a clique of a graph G. The capacity of C is defined to be (|V (G)\textbackslashC|+|D|)/2, where D is the set of vertices in V (G)\textbackslashC 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.
Publication Date: Apr-2012
Electronic Publication Date: 7-Jun-2012
Citation: Chudnovsky, Maria, Oum, Sang-Il, Seymour, Paul. (2012). Finding minimum clique capacity. COMBINATORICA, 32 (283 - 287. doi:10.1007/s00493-012-2891-9
DOI: doi:10.1007/s00493-012-2891-9
ISSN: 0209-9683
Pages: 283 - 287
Type of Material: Journal Article
Journal/Proceeding Title: COMBINATORICA
Version: Author's manuscript



Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.