首页 | 本学科首页   官方微博 | 高级检索  
     检索      


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 tk, 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.
Keywords:Corresponding author  
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号