Skip to main content

Research Repository

Advanced Search

Reducing the chromatic number by vertex or edge deletions

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

Reducing the chromatic number by vertex or edge deletions Thumbnail


Authors

C. Picouleau

B. Ries



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

Journal Article Type Conference Paper
Conference Name LAGOS 2017: The IX Latin and American Algorithms, Graphs and Optimization Symposium.
Conference Location Marseille, France
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





You might also like



Downloadable Citations