Defective List Colorings of Planar Graphs
Defective List Colorings of Planar Graphs
复制标题
DOI：
--
复制
发表时间：
1997
期刊：
影响因子：
--
通讯作者：
N. Eaton;Thomas C. Hull
中科院分区：
文献类型：
--
作者：
N. Eaton;Thomas C. Hull
本文将图的列表染色与图的亏损染色结合起来，引入了亏损列表染色的概念。我们将这些概念应用于各类平面图的顶点着色。具有缺陷d的缺陷着色是顶点的着色，使得每个颜色类对应于具有最大度至多d的导出子图。k-列表分配L是集合到顶点的分配，使得|L（v）|= k，并且L-列表着色是使得分配给v的颜色对于所有顶点v都在L（v）中的着色，并且d-亏损L-列表着色是具有亏损d的L-列表亏损着色。对于给定的图G和缺陷d，我们感兴趣的是最小数k，使得任何k-列表分配，L，i sd-缺陷L-列表可着色。我们将证明，对于外平面图，任何2-列表分配，L，有一个2-亏损的L-列表染色，这是最好的可能。我们给出了关于无三角形外平面图和二部平面图的这种形式的结果。在一般情况下，我们证明了所有的平面图是2-亏损L-列表着色的任何3-列表分配L。
We combine the concepts of list colorings of graphs with the concept of defective colorings of graphs and introduce the concept of defective list colorings. We apply these concepts to vertex colorings of various classes of planar graphs. A defective coloring with defect d is a coloring of the vertices such that each color class corresponds to an induced subgraph with maximum degree at most d .A k-list assignment L, is an assignment of sets to the vertices so that |L(v)| = k, for all vertices v and an L-list coloring is a coloring such that the color assigned to v is in L(v) for all vertices v, and a d-defective L-list coloring is an L-list defective coloring with defect d. For a given graph G and defect d, we are interested in the smallest number k such that any k-list assignment, L ,i sd-defective L-list colorable. We will show that for outerplanar graphs, any 2-list assignment, L, has a 2-defective L-list coloring, and that this is best possible. We give results of this form pertaining to triangle-free outerplanar graphs and bipartite planar graphs. In general, we prove that all planar graphs are 2-defective L-list colorable for any 3-list assignment L.