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.
|Full text:||(AM) Accepted Manuscript|
Available under License - Creative Commons Attribution Non-commercial No Derivatives.
Download PDF (302Kb)
|Publisher Web site:||https://doi.org/10.1016/j.dam.2018.08.016|
|Publisher statement:||© 2018 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:||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|