Critical Vertices and Edges in $H$-free Graphs

Daniël Paulusma, Christophe Picouleau, Bernard Ries

A vertex or edge in a graph is critical if its deletion reduces the chromatic number of the graph by 1. We consider the problems of deciding whether a graph has a critical vertex o…