最大度为6或7的稀疏图的2-距离列表染色

发布时间：2018-04-25 18:03

  本文选题：2-距离染色 + 列表染色　； 参考：《山东师范大学》2017年硕士论文

【摘要】：本文主要研究简单有限图.图G的一个正常k-2-距离染色是指映射c:V(G)→{1,2,…,k},满足:若0d_G(u,v)≤2,则|c(u)-c(v)|≥1.使得G有一个k-2-距离染色的最小k值为图G的2-距离色数,记为χ_2(G).图G的一个列表配置L是指G的每个顶点v∈V(G)分配一个可用色集L(v).设L是G的一个列表配置,若G的一个2-距离染色c对任意的v∈V(G)满足c(v)∈L(v),则称c是G的一个L-2-距离染色.若对G的任意一个满足|L(v)|≥k的列表配置L,G都有一个L-2-距离染色,则称G是k-2-距离可选的,并称ch_2(G)=min{k|G是k-2-距离可选的}为G的2-距离列表色数.1977年,Wegner证明了最大度为3的平面图的2-距离色数至多是8,并在此篇文章中提出如下猜想:对于平面图G,若?(G)=3,则χ_2(G)≤7;若4≤?(G)≤7,则χ_2(G)≤?(G)+5;若?(G)≥8,则χ_2(G)[3/2?(G)]+1.这个猜想至今并未被完全证明.本文共分为三章,主要研究了最大度分别是6,7的稀疏图的2-距离列表色数.第一章,我们介绍了论文中所涉及的一些概念和术语符号以及本文的研究背景和已有的一些结果.第二章,我们研究了稀疏图中最大度为6的图的2-距离染色的可选性,并得到下面的结果:令G为?=6的简单图,若mad(G)2+17/20(resp.mad(G)2+9/10),则ch_2(G)≤ 11(resp.ch_2(G)≤ 12).第三章,我们研究了稀疏图中最大度为7的图的2距离染色的可选性,证明了:令G为?=7的简单图,若mad(G)2+4/5(resp.mad(G)2+9/10),则ch_2(G)≤ 11(resp.ch_2(G)≤ 12).
[Abstract]:In this paper, we mainly study simple finite graphs. A normal k-2-distance coloring of graph G refers to the mapping c: VG) {1 + 2, 鈥，

本文编号：1802383