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

Full metadata record

DC Field	Value	Language
dc.contributor.author	Chudnovsky, Maria	-
dc.contributor.author	Oum, Sang-il	-
dc.contributor.author	Seymour, Paul D.	-
dc.date.accessioned	2018-07-20T15:09:05Z	-
dc.date.available	2018-07-20T15:09:05Z	-
dc.date.issued	2012-04	en_US
dc.identifier.citation	Chudnovsky, Maria, Oum, Sang-Il, Seymour, Paul. (2012). Finding minimum clique capacity. COMBINATORICA, 32 (283 - 287. doi:10.1007/s00493-012-2891-9	en_US
dc.identifier.issn	0209-9683	-
dc.identifier.uri	http://arks.princeton.edu/ark:/88435/pr1d107	-
dc.description.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.	en_US
dc.format.extent	283 - 287	en_US
dc.language.iso	en_US	en_US
dc.relation.ispartof	COMBINATORICA	en_US
dc.rights	Author's manuscript	en_US
dc.title	Finding minimum clique capacity	en_US
dc.type	Journal Article	en_US
dc.identifier.doi	doi:10.1007/s00493-012-2891-9	-
dc.date.eissued	2012-06-07	en_US
pu.type.symplectic	http://www.symplectic.co.uk/publications/atom-terms/1.0/journal-article	en_US

Files in This Item:

File	Description	Size	Format
cliquecap.pdf		58.86 kB	Adobe PDF	View/Download