[PRP17] Reducing the Chromatic Number by Vertex or Edge Deletions

Conférence Internationale avec comité de lecture : LAGOS, September 2017, Vol. 62, pp.243-248, Series ENDM, France, (DOI:

Mots clés: Graphe, Coloration

Résumé: A vertex or edge in a graph is critical if its deletion reduces the chromatic number of the graph by~1. A graph is vertex-critical if every vertex is critical and edge-critical if every edge is critical. To increase our understanding of the graph coloring problem, vertex-critical and edge-critical graphs have been studied intensively. We consider the problems of testing whether a graph has a critical vertex or 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~1. Hence, we obtain the same classification for the problem of testing if a graph has an edge whose contraction reduces the chromatic number by~1. 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.

Collaboration: LAMSADE


@inproceedings {
title="{Reducing the Chromatic Number by Vertex or Edge Deletions}",
author=" C. Picouleau and B. Ries and D. Paulusma ",
address=" France",