DMS Combinatorics Seminar

Speaker: Jeffrey Mudrock (University of South Alabama)

Title: 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. Critical and list-critical graphs occupy a prominent place in chromatic graph theory.  A k-critical graph is a graph with chromatic number k whose proper subgraphs are (k-1)-colorable.  List coloring is a well-known variation on classical vertex coloring where each vertex of a graph receives a list of available colors, and we seek to find a proper coloring of the graph such that the color used on each vertex of the graph comes from the list of colors corresponding to the vertex.  In 2008, Stiebitz, Tuza, and Voigt introduced strongly critical graphs which are graphs that are k-critical yet properly colorable with respect to every non-constant assignment that assigns list of size (k-1) to each vertex in the graph. 

In this talk we show how to construct large families of strongly critical graphs.  We also strengthen the notion of strong criticality by extending it to the framework of DP-coloring which is a generalization of list coloring that has been studied by many researchers since its introduction in 2015.  We call this strengthening of strong criticality robust criticality.  We discuss some basic properties of robustly critical graphs and give a general method for generating large families of such graphs.  As an application of these notions, we show how strong criticality (resp. robust criticality) can be used to give improved bounds on the list chromatic number (resp. DP chromatic number) of certain Cartesian products of graphs.

This is joint work with Anton Bernshteyn, Hemanshu Kaul, and Gunjan Sharma.