Tutte Colloquium - Luke Postle

Title: MAD and Local Versions of Reed's Conjecture

Abstract:

Graph coloring is a widely studied area of graph theory dating from the time of the Four Color Conjecture (now theorem). One of the most well-known conjectures in graph coloring is Reed's conjecture that the chromatic number of a graph is at most the average of its trivial lower bound, clique number, and its trivial upper bound, maximum degree plus one. In 1998, Reed proved the chromatic number is at most some nontrivial convex combination of the two bounds. Recently, my colleague Michelle Delcourt and I generalized this result to the setting of list coloring, wherein vertices want to be colored from their own list of colors. In this talk, we discuss two further generalizations joint with my Ph.D. student Thomas Kelly. First we proved under some mild assumptions that the 'local list version' of Reed's result holds, that is, where the list size of a vertex is at least some nontrivial convex combination of its degree plus one and the size of the largest clique containing it. Second, we used this local version to prove the maximum average degree ('MAD' for short) version holds, wherein the maximum degree is replaced by average degree (maximized over all subgraphs). As an application, we discuss how the latter results provides the current best known bounds for the number of edges in critical graphs without large cliques and for Hadwiger's conjecture. Joint work with Thomas Kelly.