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.
|Full text:||(AM) Accepted Manuscript|
Available under License - Creative Commons Attribution Non-commercial No Derivatives.
Download PDF (103Kb)
|Publisher Web site:||https://lipn.univ-paris13.fr/Lagos2017/|
|Publisher statement:||© 2017 This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/|
|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|