On Strongly and Robustly Critical Graphs

ABSTRACT In extremal combinatorics, it is common to focus on structures that are minimal with respect to a certain property. In particular, critical and list‐critical graphs occupy a prominent place in graph coloring theory. Stiebitz, Tuza, and Voigt introduced strongly critical graphs, i.e., graphs that are ‐critical yet ‐colorable with respect to every non‐constant assignment of lists of size . Here we strengthen this notion and extend it to the framework of DP‐coloring (or correspondence coloring) by defining robustly ‐critical graphs as those that are not ‐DP‐colorable, but only due to the fact that . We then seek general methods for constructing robustly critical graphs. Our main result is that if is a critical graph (with respect to ordinary coloring), then the join of with a sufficiently large clique is robustly critical; this is new even for strong criticality.