文章基本信息

标题：Flexible List Colorings in Graphs with Special Degeneracy Conditions
本地全文：下载
作者：Peter Bradshaw ; Masařk, Tomáš ; Ladislav Stacho 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：181
页码：1-15
DOI：10.4230/LIPIcs.ISAAC.2020.31
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：For a given Îµ > 0, we say that a graph G is Îµ-flexibly k-choosable if the following holds: for any assignment L of lists of size k on V(G), if a preferred color is requested at any set R of vertices, then at least Îµ R of these requests are satisfied by some L-coloring. We consider flexible list colorings in several graph classes with certain degeneracy conditions. We characterize the graphs of maximum degree Î" that are Îµ-flexibly Î"-choosable for some Îµ = Îµ(Î") > 0, which answers a question of DvoÅÃ¡k, Norin, and Postle [List coloring with requests, JGT 2019]. We also show that graphs of treewidth 2 are 1/3-flexibly 3-choosable, answering a question of Choi et al. [arXiv 2020], and we give conditions for list assignments by which graphs of treewidth k are 1/(k 1)-flexibly (k 1)-choosable. We show furthermore that graphs of treedepth k are 1/k-flexibly k-choosable. Finally, we introduce a notion of flexible degeneracy, which strengthens flexible choosability, and we show that apart from a well-understood class of exceptions, 3-connected non-regular graphs of maximum degree Î" are flexibly (Î" - 1)-degenerate.
关键词：Flexibility; List Coloring; Choosability; Degeneracy