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

Paulusma, D.; Picouleau, C.; Ries, B.

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.

Citation

Paulusma, D., Picouleau, C., & Ries, B. (2016, May). Reducing the clique and chromatic number via edge contractions and vertex deletions. Presented at 4th International Symposium on Combinatorial Optimization (ISCO 2016), Vietri sul Mare, Italy

• Presentation Conference Type: Conference Paper (published)
• Conference Name: 4th International Symposium on Combinatorial Optimization (ISCO 2016)
• Start Date: May 16, 2016
• End Date: May 18, 2016
• Acceptance Date: Aug 3, 2016
• Online Publication Date: Sep 10, 2016
• Publication Date: Sep 10, 2016
• Deposit Date: Oct 1, 2016
• Publicly Available Date: Sep 10, 2017
• Print ISSN: 0302-9743
• Pages: 38-49
• Series Title: Lecture notes in computer science
• Series Number: 9849
• Series ISSN: 0302-9743,1611-3349
• Book Title: Combinatorial optimization : 4th International Symposium, ISCO 2016, Vietri sul Mare, Italy, May 16-18, 2016. Revised selected papers.
• ISBN: 9783319455860
• DOI: https://doi.org/10.1007/978-3-319-45587-7_4
• Public URL: https://durham-repository.worktribe.com/output/1151210