# Finding minimum clique capacity

## Author(s): Chudnovsky, Maria; Oum, Sang-il; Seymour, Paul D.

To refer to this page use: http://arks.princeton.edu/ark:/88435/pr1d107
DC FieldValueLanguage
dc.contributor.authorChudnovsky, Maria-
dc.contributor.authorOum, Sang-il-
dc.contributor.authorSeymour, Paul D.-
dc.date.accessioned2018-07-20T15:09:05Z-
dc.date.available2018-07-20T15:09:05Z-
dc.date.issued2012-04en_US
dc.identifier.citationChudnovsky, Maria, Oum, Sang-Il, Seymour, Paul. (2012). Finding minimum clique capacity. COMBINATORICA, 32 (283 - 287. doi:10.1007/s00493-012-2891-9en_US
dc.identifier.issn0209-9683-
dc.identifier.urihttp://arks.princeton.edu/ark:/88435/pr1d107-
dc.description.abstractLet 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.en_US
dc.format.extent283 - 287en_US
dc.language.isoen_USen_US
dc.relation.ispartofCOMBINATORICAen_US
dc.rightsAuthor's manuscripten_US
dc.titleFinding minimum clique capacityen_US
dc.typeJournal Articleen_US
dc.identifier.doidoi:10.1007/s00493-012-2891-9-
dc.date.eissued2012-06-07en_US
pu.type.symplectichttp://www.symplectic.co.uk/publications/atom-terms/1.0/journal-articleen_US

Files in This Item:
File Description SizeFormat