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:

Reducing the chromatic number by vertex or edge deletions.

Picouleau, C. and Paulusma, D. and Ries, B. (2017) 'Reducing the chromatic number by vertex or edge deletions.', Electronic notes in discrete mathematics., 62 . pp. 243-248.


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.

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:© 2017 This manuscript version is made available under the CC-BY-NC-ND 4.0 license
Date accepted:23 May 2017
Date deposited:06 June 2017
Date of first online publication:26 October 2017
Date first made open access:26 April 2019

Save or Share this output

Look up in GoogleScholar