关于Reed列表染色猜想的一些结果.pdfVIP

年 月 纯粹数学与应用数学 **) $ ]7[(**) 第 卷第 期 @ OPQ7RS8TTUV78WRXY7ZRXV[\ ^_U(‘_(@ 关于!#列表染色猜想的一些结果 $% 许 洋 朱晓颖 陈 藏 % % 莱阳农学院数学系 山东 青岛 中国矿业大学数学系 江苏 徐州 ’$( % ))$*+,( % $**-. 摘 要 构造了一个图 给 的每个顶点 一个颜色列表 使得每个列表 的大小至 / 0% 0 1 % 2 1 少为每个顶点 的邻域 与每个 交集的最大数目 但是这个图不存在一个正 ’. % 1 3 1 4 0 5 常的列表染色 从而推翻了 的一个猜想 % 6778 9 关 键 词 列表染色 可选择的 点 色度 / , , : 中图分类号/ $=9 文献标识码/ 文章编号/$**-:$?’**).*@:*):*@ ; B 引 言 设 为一个图 我们分别用 和 表示 的顶点集 边集和最大度 0 % 4’0.%C’0. D ’0. 0 % 93 ’1. 0 表示与顶点相邻的顶点集合 即顶点 的邻域 一个顶点的度 其他未标明的 % 1 9 E’1.F G3 ’1.G9 0 符号和术语均见文H$I9 我们给 的每一个顶点 一个颜色列表 如果存在 的一个染色 满足 对任意顶 0 1 2 % 0 J /’$. 1 点 有 对任意邻接的两个顶点 有 则我们 1K 4’0.% 5’1.K 2 %’. L%1K 4’0.% 5’1.M 5’L.% 1 称 是可正常列表染色的 0 显然 如果每个顶点的颜色列表 至少为 那么我们可以按照贪婪算法 给 %