Critical vertices and edges in H-free graphs

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

Abstract

A vertex or edge in a graph is critical if its deletion reduces the chromatic number of the graph by one. We consider the problems of deciding whether a graph has a critical vertex or edge, respectively. We give a complexity dichotomy for both problems restricted to -free graphs, that is, graphs with no induced subgraph isomorphic to . Moreover, we show that an edge is critical if and only if its contraction reduces the chromatic number by one. Hence, we also obtain a complexity dichotomy for the problem of deciding if a graph has an edge whose contraction reduces the chromatic number by one.

Citation

Paulusma, D., Picouleau, C., & Ries, B. (2019). Critical vertices and edges in H-free graphs. Discrete Applied Mathematics, 257, 361-367. https://doi.org/10.1016/j.dam.2018.08.016

• Journal Article Type: Article
• Acceptance Date: Aug 28, 2018
• Online Publication Date: Oct 11, 2018
• Publication Date: Mar 31, 2019
• Deposit Date: Sep 19, 2018
• Publicly Available Date: Oct 11, 2019
• Journal: Discrete Applied Mathematics
• Print ISSN: 0166-218X
• Electronic ISSN: 1872-6771
• Publisher: Elsevier
• Peer Reviewed: Peer Reviewed
• Volume: 257
• Pages: 361-367
• DOI: https://doi.org/10.1016/j.dam.2018.08.016
• Public URL: https://durham-repository.worktribe.com/output/1314370