C. Picouleau
Reducing the chromatic number by vertex or edge deletions
Picouleau, C.; Paulusma, D.; Ries, B.
Abstract
A vertex or an edge in a graph is critical if its deletion reduces the chromatic number of the graph by one. We consider the problems of testing whether a graph has a critical vertex or a critical edge, respectively. We give a complete classification of the complexity of both problems for H-free graphs, that is, graphs with no induced subgraph isomorphic to H. Moreover, we show that an edge is critical if and only if its contraction reduces the chromatic number by one. Hence, we obtain the same classification for the problem of testing if a graph has an edge whose contraction reduces the chromatic number by one. As a consequence of our results, we are also able to complete the complexity classification of the more general vertex deletion and edge contraction blocker problems for H-free graphs when the graph parameter is the chromatic number.
Citation
Picouleau, C., Paulusma, D., & Ries, B. (2017). Reducing the chromatic number by vertex or edge deletions. Electronic Notes in Discrete Mathematics, 62, 243-248. https://doi.org/10.1016/j.endm.2017.10.042
Presentation Conference Type | Conference Paper (published) |
---|---|
Conference Name | LAGOS 2017: The IX Latin and American Algorithms, Graphs and Optimization Symposium. |
Acceptance Date | May 23, 2017 |
Online Publication Date | Oct 26, 2017 |
Publication Date | Nov 1, 2017 |
Deposit Date | Jun 2, 2017 |
Publicly Available Date | Oct 26, 2018 |
Journal | Electronic Notes in Discrete Mathematics |
Print ISSN | 1571-0653 |
Publisher | Elsevier |
Peer Reviewed | Peer Reviewed |
Volume | 62 |
Pages | 243-248 |
Series Title | Electronic Notes in Discrete Mathematics |
DOI | https://doi.org/10.1016/j.endm.2017.10.042 |
Public URL | https://durham-repository.worktribe.com/output/1148379 |
Files
Accepted Journal Article
(105 Kb)
PDF
Publisher Licence URL
http://creativecommons.org/licenses/by-nc-nd/4.0/
Copyright Statement
© 2017 This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/
You might also like
Computing balanced solutions for large international kidney exchange schemes
(2024)
Journal Article
An Algorithmic Framework for Locally Constrained Homomorphisms
(2024)
Journal Article
Matching cuts in graphs of high girth and H-free graphs
(2023)
Presentation / Conference Contribution
Solving problems on generalized convex graphs via mim-width
(2023)
Journal Article
Dichotomies for Maximum Matching Cut: H-Freeness, Bounded Diameter, Bounded Radius
(2023)
Presentation / Conference Contribution
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