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).
Abstract
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) |
Status: | Peer-reviewed |
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
Export: | |
Look up in GoogleScholar |