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

作者：许洋; 朱晓颖; 陈藏

来源：纯粹数学与应用数学, 2006, (04): 556-559+564.

• 列表染色
• 可选择的
• 点-色度 list coloring
• choosability
• vertex-color degree

构造了一个图G,给G的每个顶点v一个颜色列表,使得每个列表Lv的大小至少为每个顶点v的邻域NG(v)与每个Vc交集的最大数目,但是这个图不存在一个正常的列表染色,从而推翻了R eed的一个猜想.

• 单位
  中国矿业大学; 中国矿业大学（北京）; 青岛农业大学