Finding minimum clique capacity

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.