In classical vertex coloring we wish to color the vertices of a graph G with up to m colors from [m] so that adjacent vertices receive different colors, a so-called 'proper m-coloring'. List coloring is a well-known variation of classical vertex coloring that was introduced independently by Vizing and Erdos, Rubin, and Taylor in the 1970s. For list coloring, we associate a 'list assignment' L with a graph G such that each vertex v in G is assigned a list of colors L(v) (we say L is a list assignment for G). An 'L-coloring' of G is a function f with domain V(G) such that f(v) is a member of L(v) for every vertex v in G. We say that G is 'L-colorable' if there exists a proper L-coloring of G: an L-coloring where adjacent vertices receive different colors. A list assignment L for G is called a 'k-assignment' if |L(v)|=k for each vertex v in G. We say G is 'k-choosable' or 'k-list colorable' if G is L-colorable whenever L is a k-assignment for G. The 'list chromatic number' of G is the smallest k such that G is k-choosable.  

 

Flexible list coloring was introduced by [Dvorak, Norin, and Postle, 2019] in order to address a situation in list coloring where we still seek a proper list coloring, but a preferred color is given for some subset of vertices and we wish to color as many vertices in this subset with its preferred colored as possible, a flexible version of the classical precoloring extension problem. In this talk, we explore the notion of flexible list colorings. We describe easy-to-follow proofs of two general results and pose several open questions. 

 

This talk is based on a joint work with Hemanshu Kaul, Jeffrey Mudrock, and Michael Pelsmajer. 

 

Short Bio: Rogers Mathew is an associate professor in the Department of Computer Science and Engineering, IIT Hyderabad. He works in graphs theory, combinatorics, and graph algorithms.