Professor Daniel Paulusma daniel.paulusma@durham.ac.uk
Professor
Raffaele Cerulli
Editor
Satoru Fujishige
Editor
A. Ridha Mahjoub
Editor
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.
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 |
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 |
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
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
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
Dichotomies for Maximum Matching Cut: H-Freeness, Bounded Diameter, Bounded Radius
(2023)
Conference Proceeding
About Durham Research Online (DRO)
Administrator e-mail: dro.admin@durham.ac.uk
This application uses the following open-source libraries:
Apache License Version 2.0 (http://www.apache.org/licenses/)
Apache License Version 2.0 (http://www.apache.org/licenses/)
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