A list analogue of equitable coloring
A list analogue of equitable coloring
复制标题
DOI：
10.1002/jgt.v44:3
复制
发表时间：
2003-11
影响因子：
0.9
通讯作者：
A. Kostochka;M. Pelsmajer;D. West
中科院分区：
文献类型：
--
作者：
A. Kostochka;M. Pelsmajer;D. West
给定给定图G的顶点的可用颜色列表，列表着色是G的一种真着色，使得每个顶点上的颜色都是从它的列表中选择的。如果列表的大小都是k，则列表着色是公平的，如果每个颜色最多出现在$\lceil n（G）/k \rceil$顶点上。一个图是公平k-可选的，如果这样的着色存在，只要列表都有大小k。本文证明了当$k \ge {\Delta（G），n（G）/2}$时G是公平k-可选的，除非G包含$K_{k+1}$或k是奇数且$G=K_{k，k}$.对于森林，阈值提高到$k \ge 1+\Delta（G）/2$。如果G是2-退化图（给定k ≥ 5）或连通区间图（不包括$K_{k+1}$），则G是公平k-可选的，当$k\ge \Delta（G）$。© 2003 Wiley Periodicals，Inc. J Graph Theory 44：166-177，2003
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 $\lceil n (G)/k \rceil$ 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 \ge {\rm max} \{ {\Delta (G),n(G)/2}\}$ unless G contains $K_{k+1}$ or k is odd and $G=K_{k,k}$. For forests, the threshold improves to $k \ge 1+\Delta (G)/2$. If G is a 2‐degenerate graph (given k ≥ 5) or a connected interval graph (other than $K_{k+1}$), then G is equitably k‐choosable when $k\ge \Delta(G)$. © 2003 Wiley Periodicals, Inc. J Graph Theory 44: 166–177, 2003