Skip to main content

Research Repository

Advanced Search

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

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

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


Authors

C. Picouleau

B. Ries



Contributors

Raffaele Cerulli
Editor

Satoru Fujishige
Editor

A. Ridha Mahjoub
Editor

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). Reducing the clique and chromatic number via edge contractions and vertex deletions. In R. Cerulli, S. Fujishige, & A. R. Mahjoub (Eds.), Combinatorial optimization : 4th International Symposium, ISCO 2016, Vietri sul Mare, Italy, May 16-18, 2016. Revised selected papers (38-49). https://doi.org/10.1007/978-3-319-45587-7_4

Conference Name 4th International Symposium on Combinatorial Optimization (ISCO 2016)
Conference Location Vietri sul Mare, Italy
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 Mar 29, 2024
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

Files





You might also like



Downloadable Citations