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 (288Kb)
|Publisher Web site:||http://dx.doi.org/10.1007/978-3-319-45587-7_4|
|Publisher statement:||The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-319-45587-7_4|
|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|