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. Reducing the chromatic number by vertex or edge deletions. Presented at LAGOS 2017: The IX Latin and American Algorithms, Graphs and Optimization Symposium., Marseille, France

• 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