pith. sign in

arxiv: 1512.07847 · v1 · pith:YGANOW76new · submitted 2015-12-24 · 🧮 math.CO

Choosability with union separation

classification 🧮 math.CO
keywords listchoosablecoloringassignmentchoosabilitygraphseparationunion
0
0 comments X
read the original 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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.