91×ÔÅÄ

Speaker: , University of South Alabama

Title: On Maximizing Satisfied Vertex Requests in List Coloring

Abstract:
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.