Professor Daniel Paulusma daniel.paulusma@durham.ac.uk
Professor
Reducing the clique and chromatic number via edge contractions and vertex deletions
Paulusma, D.; Picouleau, C.; Ries, B.
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
Accepted Conference Proceeding
(295 Kb)
PDF
Copyright Statement
The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-319-45587-7_4
You might also like
Matching cuts in graphs of high girth and H-free graphs
(2023)
Conference Proceeding
Solving problems on generalized convex graphs via mim-width
(2023)
Journal Article
An algorithmic framework for locally constrained homomorphisms
(2023)
Journal Article
On the price of independence for vertex cover, feedback vertex set and odd cycle transversal
(2023)
Journal Article
Computing Subset Vertex Covers in H-Free Graphs
(2023)
Conference Proceeding
Downloadable Citations
About Durham Research Online (DRO)
Administrator e-mail: dro.admin@durham.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search