圖的線性染色.pdf

1、用G=(V, E)表示一個(gè)頂點(diǎn)集為V，邊集為E的有限、簡單無向圖，{1，2，…，k)表示k個(gè)顏色的集合.G的一個(gè)正常k-染色是一個(gè)映射φ：V→(1，2…，k)使得相鄰的頂點(diǎn)接受不同的色.如果G有一個(gè)正常k-染色，則稱G是k-可染的.G的色數(shù)x(G)是使得G是正常k-可染的最小的非負(fù)整數(shù)七.如果圖G的一個(gè)正常染色滿足染任意兩種顏色的頂點(diǎn)集合導(dǎo)出的子圖是一些點(diǎn)不交的路的并，則稱這個(gè)正常染色為圖G的線性染色.圖G的線性色數(shù)用1c(G)表示，是

2、指G的所有線性染色中所用的最少顏色的個(gè)數(shù). 1998年，Yuster[1]首先研究了圖的線性染色.證明了任意圖G的線性色數(shù)滿足1c(G)=○(△3/2)，且構(gòu)造出了一類圖使得1c(G)=Ω(△3/2).事實(shí)上，這個(gè)概念是圖的無圈染色的一種特殊情形.無斟染色的概念是由Grunbaum[2]提出的，圖G的一個(gè)無圈染色是G的一個(gè)正常染色，使得染任意兩種顏色的頂點(diǎn)集合導(dǎo)出的子圖是一個(gè)森林. 本學(xué)位論文主要是對前人的一些研究結(jié)果的

3、改進(jìn)和擴(kuò)充，對非負(fù)特征圖、平面圖和一些度數(shù)較小的圖的的研究.設(shè)△(G)和g(G)分別表示圖G的最大度和圍長. 在第一章中，我們給出本文所用到的基本概念，簡述了相關(guān)領(lǐng)域的研究現(xiàn)狀以及呈現(xiàn)了本文的主要結(jié)果. 在第二章中，我們證明了下面的結(jié)果： (1)對于每一個(gè)非負(fù)特征圖G，若存在一個(gè)有序?qū)?△，g)∈{(13，7)，(9，8)，(7，9)，(5，10)，(3，13))使得△(G)≥△且g(G)≥g，則1c(G)=[△