A list analogue of equitable coloring
A list analogue of equitable coloring
复制标题
DOI：
10.1002/jgt.10137
复制
发表时间：
2003-11-01
影响因子：
0.9
通讯作者：
West, DB
中科院分区：
文献类型：
--
作者：
Kostochka, AV;Pelsmajer, MJ;West, DB
给定给定图G的顶点的可用颜色列表，列表着色是G的一种真着色，使得每个顶点上的颜色都是从它的列表中选择的。如果列表的大小都是k，则列表着色是公平的，如果每种颜色最多出现在[n（G）/k]个顶点上。一个图是公平k-可选的，如果这样的着色存在，只要列表都有大小k。证明了当k ≥ max{Delta（G），n（G）/2}时，G是公平k-可选的，除非G包含Kk+1或k是奇数且G = K-k，K-k.对于森林，阈值改进为k大于或等于1 + Delta（G）/2。若G是2-退化图（k ≥ 5）或连通区间图（Kk+1除外），则当k ≥ Delta（G）时G是公平k-可选的. (C)2003 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 [n(G)/k] vertices. A graph is equitably k-choosable if such a coloring exists whenever the lists all have size k. We prove that G is equitably k-choosable when k greater than or equal to max{Delta(G),n(G)/2} unless G contains Kk+1 or k is odd and G = K-k,K-k. For forests, the threshold improves to k greater than or equal to 1 + Delta(G)/2. If G is a 2-degenerate graph (given k greater than or equal to 5) or a connected interval graph (other than Kk+1), then G is equitably k-choosable when k greater than or equal to Delta (G). (C) 2003 Wiley Periodicals, Inc.