Abstract
Let C be a clique of a graph G. The capacity of C is defined to be (|V (G)\C|+|D|)/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.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
M. Chudnovsky and P. Seymour: Packing seagulls, Combinatorica, this issue.
J. E. Hopcroft and R. M. Karp: An n 5/2 algorithm for maximum matchings in bipartite graphs, SIAM Journal on Computing 2 (1973), 225–231.
Author information
Authors and Affiliations
Corresponding author
Additional information
Supported by NSF grants DMS-1001091 and IIS-1117631.
Supported by the Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Education, Science and Technology (No. 2011-0011653) and a TJ Park Junior Faculty Fellowship.
Supported by ONR grant N00014-10-1-0680 and NSF grant DMS-0901075.
Rights and permissions
About this article
Cite this article
Chudnovsky, M., Oum, SI. & Seymour, P. Finding minimum clique capacity. Combinatorica 32, 283–287 (2012). https://doi.org/10.1007/s00493-012-2891-9
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00493-012-2891-9