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 |
