最大度為6或7的稀疏圖的2-距離列表染色.pdf

1、本文主要研究簡單有限圖.圖G的一個(gè)正常fc-2-距離染色是指映射C：F(G)→{1，2,…, k],滿足：若0< dG(u,v)<2,則|c(u)- c(v)|>1.使得G有一個(gè)k-2-距離染色的最小k值為圖G的2-距離色數(shù)，記為x2(G).
　　圖G的一個(gè)列表配置L是指G的每個(gè)頂點(diǎn)v∈F(G)分配一個(gè)可用色集L(v).設(shè)L是G的一個(gè)列表配置，若G的一個(gè)2-距離染色c對任意的v∈ F( G)滿足c(v)∈ L(v),則稱c是G的一

2、個(gè)L-2-距離染色.若對G的任意一個(gè)滿足|L(v)|> k的列表配置L, G都有一個(gè)L-2-距離染色，則稱G是k-2-距離可選的，并稱ch2( G)=min{k(G)是fc-2-距離可選的}為G的2-距離列表色數(shù).
　　1977年，W egner證明了最大度為3的平面圖的2-距離色數(shù)至多是8,并在此篇文章中提出如下猜想：對于平面圖G,若△(G)=3,則X2(G)<7;若4<△(G)<7,則X2(G)<△(G)+5;若△(G)>8,

3、則X2(G)<[-/2△(G)J]+1.這個(gè)猜想至今并未被完全證明.
　　本文共分為三章，主要研究了最大度分別是6,7的稀疏圖的2-距離列表色數(shù).第一章，我們介紹了論文中所涉及的一些概念和術(shù)語符號以及本文的研究背景和已有的一些結(jié)果.
　　第二章，我們研究了稀疏圖中最大度為6的圖的2-距離染色的可選性，并得到下面的結(jié)果:令G為△=6的簡單圖,若mad(G)<2+17/20(resp. mad(G)<2+9/10),則ch2(G