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

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

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