本文選題：2-距離染色 + 列表染色��； 參考：《山東師范大學(xué)》2017年碩士論文

【摘要】：本文主要研究簡單有限圖.圖G的一個(gè)正常k-2-距離染色是指映射c:V(G)→{1,2,…,k},滿足:若0d_G(u,v)≤2,則|c(u)-c(v)|≥1.使得G有一個(gè)k-2-距離染色的最小k值為圖G的2-距離色數(shù),記為χ_2(G).圖G的一個(gè)列表配置L是指G的每個(gè)頂點(diǎn)v∈V(G)分配一個(gè)可用色集L(v).設(shè)L是G的一個(gè)列表配置,若G的一個(gè)2-距離染色c對任意的v∈V(G)滿足c(v)∈L(v),則稱c是G的一個(gè)L-2-距離染色.若對G的任意一個(gè)滿足|L(v)|≥k的列表配置L,G都有一個(gè)L-2-距離染色,則稱G是k-2-距離可選的,并稱ch_2(G)=min{k|G是k-2-距離可選的}為G的2-距離列表色數(shù).1977年,Wegner證明了最大度為3的平面圖的2-距離色數(shù)至多是8,并在此篇文章中提出如下猜想:對于平面圖G,若?(G)=3,則χ_2(G)≤7;若4≤?(G)≤7,則χ_2(G)≤?(G)+5;若?(G)≥8,則χ_2(G)[3/2?(G)]+1.這個(gè)猜想至今并未被完全證明.本文共分為三章,主要研究了最大度分別是6,7的稀疏圖的2-距離列表色數(shù).第一章,我們介紹了論文中所涉及的一些概念和術(shù)語符號以及本文的研究背景和已有的一些結(jié)果.第二章,我們研究了稀疏圖中最大度為6的圖的2-距離染色的可選性,并得到下面的結(jié)果:令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