Equitable list-coloring for graphs for maximum Degree 3
Equitable list-coloring for graphs for maximum Degree 3
复制标题
DOI：
10.1002/jgt.20011
复制
发表时间：
2004-09-01
影响因子：
0.9
通讯作者：
Pelsmajer, MJ
中科院分区：
文献类型：
--
作者：
Pelsmajer, MJ
给定分配给图 G 的顶点的可用颜色列表，列表着色是 G 的适当着色，使得每个顶点上的颜色都是从其列表中选择的。如果列表的大小均为 k，则如果每种颜色最多出现在 [|V(G)|/k] 个顶点上，则列表着色是公平的。如果每当列表的大小都为 k 时就存在这种着色，那么图就公平地是 k 可选择的。 Kostochka、Pelsmajer 和 West 引入了这一概念，并推测当 k > Delta(G) 时，G 是公平 k 可选择的。我们在 Delta(G) = 3 时证明了这一点。我们还表明，当 k 大于或等于 Delta(G)(Delta(G)- 1)/2 + 2 时，每个图 G 都是公平 k 可选择的。(C) 2004 Wiley periodicals, Inc.
Given lists of available colors assigned to the vertices of a graph G, a list coloring is a proper coloring of G such that the color on each vertex is chosen from its list. If the lists all have size k, then a list coloring is equitable if each color appears on at most [|V(G)|/k] vertices. A graph is equitably k-choosable if such a coloring exists whenever the lists all have size k. Kostochka, Pelsmajer, and West introduced this notion and conjectured that G is equitably k-choosable for k > Delta(G). We prove this for Delta(G) = 3. We also show that every graph G is equitably k-choosable for k greater than or equal to Delta(G)(Delta(G)- 1)/2 + 2. (C) 2004 Wiley Periodicals, Inc.