We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.

Durham Research Online
You are in:

Critical vertices and edges in H-free graphs.

Paulusma, D. and Picouleau, C. and Ries, B. (2019) 'Critical vertices and edges in H-free graphs.', Discrete applied mathematics., 257 . pp. 361-367.


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.

Item Type:Article
Full text:(AM) Accepted Manuscript
Available under License - Creative Commons Attribution Non-commercial No Derivatives.
Download PDF
Publisher Web site:
Publisher statement:© 2018 This manuscript version is made available under the CC-BY-NC-ND 4.0 license
Date accepted:28 August 2018
Date deposited:20 September 2018
Date of first online publication:11 October 2018
Date first made open access:11 October 2019

Save or Share this output

Look up in GoogleScholar