Choosability with union separation |
| |
Authors: | Mohit Kumbhat Kevin Moss Derrick Stolee |
| |
Institution: | 1. Department of Mathematics, University of Nevada, Reno, NV, USA;2. Department of Mathematics, Iowa State University, Ames, IA, USA;3. Microsoft, Raleigh, NC, USA |
| |
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 , a -list assignment is a list assignment where for all vertices and for all edges . A graph is -choosable if there is a proper coloring for every -list assignment. We explore this concept through examples of graphs that are not -choosable, demonstrating sparsity conditions that imply a graph is -choosable, and proving that all planar graphs are -choosable and -choosable. |
| |
Keywords: | Corresponding author |
本文献已被 ScienceDirect 等数据库收录! |
|