Choosability with union separation

Abstract

List coloring generalizes graph coloring by requiring the color of a vertex to be selected from a list of colors specific to that vertex. One refinement of list coloring, called choosability with separation, requires that the intersection of adjacent lists is sufficiently small. We introduce a new refinement, called choosability with union separation, where we require that the union of adjacent lists is sufficiently large. For \(t \geq k\), a \((k,t)\)-list assignment is a list assignment \(L\) where \(|L(v)| \geq k\) for all vertices \(v\) and \(|L(u)\cup L(v)| \geq t\) for all edges \(uv\). A graph is \((k,t)\)-choosable if there is a proper coloring for every \((k,t)\)-list assignment. We explore this concept through examples of graphs that are not \((k,t)\)-choosable, demonstrating sparsity conditions that imply a graph is \((k,t)\)-choosable, and proving that all planar graphs are \((3,11)\)-choosable and \((4,9)\)-choosable.