Department of
Applied
Mathematics

Toward a Local Version of Reed's Conjecture on omega, Delta, and chi

Tom Kelly

Abstract

(joint work with Luke Postle)

Bounding the chromatic number and list-chromatic number of graphs has been widely studied. For a graph G, the "trivial lower-bound" on both parameters is the size of a largest clique in G, denoted omega(G), and the "trivial upper-bound" is one plus the maximum degree of a vertex in G, denoted Delta(G). In 1998, Reed conjectured that for every graph the chromatic number is bounded above by the average of these two trivial bounds, up to rounding. It is natural to ask if this bound also holds for the list-chromatic number. In this talk, we ask if something stronger is true, namely, if L is a list-assignment for a graph G in which the number of colors available to each vertex is at least the average of its degree and the size of the largest clique in its neighborhood, rounded up, is G L-colorable? We will discuss some of what is known about Reed's Conjecture and present some progress towards answering this question.