EQUITABLE LIST COLORING OF GRAPHS
EQUITABLE LIST COLORING OF GRAPHS
复制标题
DOI：
10.11650/tjm.8.2004.1088
复制
发表时间：
2004-01
影响因子：
0.4
通讯作者：
Weifan Wang;Ko-Wei Lih
中科院分区：
文献类型：
--
作者：
Weifan Wang;Ko-Wei Lih
如果对于任何 $k$ 均匀列表分配 $L$，$G$ 承认适当的着色 $\pi$，使得 $\pi(v)\in L(v)$ 对于所有 $v\in V(G)$ 且每种颜色最多出现在 $\lceil |G|/k\rceil$ 顶点上，则图 $G$ 是公平的 $k$ 可选择的。在[8]中推测，只要$k\ge \Delta+1$，每个具有最大度$\Delta$的图$G$都是$k$可选择的。我们在以下情况下证明猜想： (i) $\Delta \le 3$; (ii) $k\ge (\Delta-1)^2$。此外，还完全表征了 2 个可选图。
A graph $G$ is equitably $k$-choosable if, for any $k$-uniform list assignment $L$, $G$ admits a proper coloring $\pi$ such that $\pi(v)\in L(v)$ for all $v\in V(G)$ and each color appears on at most $\lceil |G|/k\rceil$ vertices. It was conjectured in [8] that every graph $G$ with maximum degree $\Delta$ is equitably $k$-choosable whenever $k\ge \Delta+1$. We prove the conjecture for the following cases: (i) $\Delta \le 3$; (ii) $k\ge (\Delta-1)^2$. Moreover, equitably 2-choosable graphs are completely characterized.