کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
8903055 | 1632401 | 2018 | 6 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Choosability with union separation
ترجمه فارسی عنوان
انتخاب با جدایی اتحادیه
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
چکیده انگلیسی
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.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 341, Issue 3, March 2018, Pages 600-605
Journal: Discrete Mathematics - Volume 341, Issue 3, March 2018, Pages 600-605
نویسندگان
Mohit Kumbhat, Kevin Moss, Derrick Stolee,