We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.

Durham Research Online
You are in:

Reducing the clique and chromatic number via edge contractions and vertex deletions.

Paulusma, D. and Picouleau, C. and Ries, B. (2016) 'Reducing the clique and chromatic number via edge contractions and vertex deletions.', in Combinatorial optimization : 4th International Symposium, ISCO 2016, Vietri sul Mare, Italy, May 16-18, 2016. Revised selected papers. Cham, Switzerland: Springer, pp. 38-49. Lecture notes in computer science. (9849).


We consider the following problem: can a certain graph parameter of some given graph G be reduced by at least d, for some integer d, via at most k graph operations from some specified set S, for some given integer k? As graph parameters we take the chromatic number and the clique number. We let the set S consist of either an edge contraction or a vertex deletion. As all these problems are NP-complete for general graphs even if d is fixed, we restrict the input graph G to some special graph class. We continue a line of research that considers these problems for subclasses of perfect graphs, but our main results are full classifications, from a computational complexity point of view, for graph classes characterized by forbidding a single induced connected subgraph H.

Item Type:Book chapter
Full text:(AM) Accepted Manuscript
Download PDF
Publisher Web site:
Publisher statement:The final publication is available at Springer via
Date accepted:03 August 2016
Date deposited:03 October 2016
Date of first online publication:10 September 2016
Date first made open access:10 September 2017

Save or Share this output

Look up in GoogleScholar