ÌÒ×ÓÊÓƵAPP

Flexible list coloring was introduced by Dvořák, Norin, and Postle in 2019 to address a situation in list coloring where we still seek a proper list coloring, but each vertex may have a preferred color assigned to it, and for those vertices we wish to color as many of them as possible with their preferred colors. This can be thought of as a relaxation of the classical pre-coloring extension problem. Specifically, suppose G is a graph and L is a list assignment for G. A request of L is a function r with nonempty domain D ⊆ V(G) such that r(v) is in L(v) for each v in D. We say G is (k, ε)-flexible if there exists a proper L-coloring f of G such that f(v) = r(v) for at least ε|D| vertices whenever L is a k-assignment for G and r is a request of L with domain D.

Much of the literature on flexible list coloring focuses on showing that for a fixed graph G and k there exists an ε > 0 such that G is (k, ε)-flexible, but it is natural to try to find the largest possible ε for which G is (k, ε)-flexible. In this talk we present results on finding the maximum such ε for fixed G and k. Our results reveal a connection to the Hall ratio, which was introduced in 1997 by Hilton, Johnson Jr., and Leonard under the name fractional Hall-condition number. This is joint work with Timothy Bennett, Michael Bowdoin, Haley Broadus, Daniel Hodgins, Adam Nusair, Gabriel Sharbel, and Joshua Silverman.

Discrete Applied Math Seminar