2015/12/24 by Mohit Kumbhat, Kumbhat, Mohit, Kevin Moss +3 · 1 citation
Mathematics · #05C15 #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:05C15
paper · pdf · doi:10.48550/arxiv.1512.07847
10 pages, 2 figures
arxiv created 2015/12/24 · arxiv updated 2015/12/25
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 ≥ k, a (k,t)-list assignment is a list assignment L where |L(v)| ≥ k for all vertices v and |L(u)∪ L(v)| ≥ 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.