圖的定向染色和平方染色.pdf

1、本文結(jié)合圖的定向染色和L(j，k)-標(biāo)號問題，給出了圖的2-有向路色數(shù)的概念，并且研究了一些圖類的2-有向路色數(shù)和平方色數(shù). 設(shè)→X2(→G)表示定向圖→G的2-有向路色數(shù)，χ(G2)表示圖G的平方色數(shù). 第一章，給出本文所用到的基本概念，簡述了相關(guān)領(lǐng)域的研究現(xiàn)狀以及呈現(xiàn)了本文的主要結(jié)果. 第二章，首先給出一些圖的2-有向路色數(shù)的性質(zhì)和基本結(jié)果.隨后證明了對每一個定向Halin圖→G，有→X2(→G)≤7，并且證

2、明此上界是緊的，例如定向輪圖可達(dá)到這個上界值. 第三章，對幾類循環(huán)圖，研究了其2-有向路色數(shù)與平方色數(shù)之間的聯(lián)系，得到了下面兩個結(jié)論： (1)G(n；1，2)，G(n；1，2，3)及G(n；1，3)的2-有向路色數(shù)與平方色數(shù)相等. (2)對某些n，G(n；1，4)的2-有向路色數(shù)嚴(yán)格小于它的平方色數(shù). 第四章，考慮了圖的定向染色問題.對一些有限圍長的目標(biāo)圖，構(gòu)造出相應(yīng)的給定圍長的圖，從而得到兩者之間的同態(tài)