研究報告
| 學年 | 97 |
|---|---|
| 學期 | 1 |
| 出版（發表）日期 | 2009-01-01 |
| 作品名稱 | 圖的多重著色數和圖的分數著色數之研究 |
| 作品名稱（其他語言） | The Study of the Kth Chromatic Number of Graphs and the Fractional Chromatic Number of Graphs. |
| 著者 | 潘志實 |
| 單位 | 淡江大學數學學系 |
| 描述 | 計畫編號：NSC98-2115-M032-003 研究期間：200908~201007 研究經費：294,000 |
| 委託單位 | 行政院國家科學委員會 |
| 摘要 | 圖的多重著色是Stahl在[13]中提出，在文獻中也被廣泛的研究。假定kn≥為正整數。令表示][n}1,,1,0{−nL的集合且為所有的⎟⎟⎠⎞⎜⎜⎝⎛kn][][nk元子集的集合。給定圖G正整數nk,，G的k欄n著色是一個映射→Vf:得G任意的邊⎟⎟⎠⎞⎜⎜⎝⎛kn][的xy，∅=∩))y((fxf。 G的k重著色數}colouring- fold- a has :{min)(nkGnGk=χ。而1欄著色就是傳統的著色,這表示nn)()(1GGχχ=。所以)(Gkχ是)(Gχ的推廣。且的分數著色數G},,2,1:/)(inf{)(K==kkGGkfχχ。 因此)(G)(Gfχχ≤。 在過去的文獻中，我們知道)()(GGfχχ−是可以任意大的。但是，由[10]觀察)()(GGfχχ−可以任意大的圖類很少。其中一種是Kneser 圖。 在[11]中，我們知道當kn≥2, knkn/)),Kf((=χ。另一方面，根據 Lovász定理[8], 2+2)),(−=(knknKχ. 這證明)()(GGfχχ−可以任意大，當G是Kneser 圖。 另一圖是藤蔓結構的圖。假定),(EVG=為一圖且為整數。的藤蔓0≥mGm)(Gmμ是一個圖，其點集為}{(u])1[mV∪+×，其中如果Exy∈且1=−ji或是Exy∈且0==ji，則),)(,(jyix為)(Gmμ的邊。最後在加一個點和所有個u),(mx相連。令)),,2mK(),Gtm(,,321mmmK(,Gtm1mμμμ=。給定任意個圖H，在[3,9,12,14]證明了當,i,1≥im1HG≥=0且)1−(=tGmtGtμ，)(G)(Gfχχ−可以任意大，然而)tG(f)(tGχχ−確切的值卻是難以計算的。 隨這k多重著色數是著色數的推廣，很自然的會研究這些圖的k多重著色數。計算Kneser圖的k多重著色數的問題，等價於計算Kneser同構的存再性問題，這在過去的文獻[2,4,13]已有被研究過。目前知道當rqkk−=',≥q且'0kr<≤是整數時，rqnkn2'))','(K(−≤χ。在[13]中猜想那等號是成立的。 當0=r或時，這猜想是對的，但是其他的情形還不知道。還有很多其他的有關這方面的問題還沒被解決。這個計畫主要針對這方面圖的k多重著色數，並試著去解決一些問題。 Multiple colouring of graphs was introduced by Stahl in [13], and has been studied extensively in the literature. Suppose kn≥ are positive integers. We denote by the set ][n}1,,1,0{−nL and denote by the family of all ⎟⎟⎠⎞⎜⎜⎝⎛kn][k-subsets of . Given a graph and positive integers ]n[Gnk,, a k-fold -colouring of is a mapping nG→Vf:⎟⎟⎠⎞kn][⎜⎜⎝⎛ such that for any edge xy of G, ∅=)∩()y(fxf. The kth chromatic number of G is defined as } has colouring- fold- ank:G{minn)(G=kχ. As a 1-fold -colouring is just an -colouring, we have nn)()(1GGχχ=. So )(Gkχ is a generalization of )(Gχ. The fractional chromatic number of G is defined as },,2,1K=:/kk)(Ginf{)(=Gkfχχ. Thus )()G(fGχχ≤. It is known that the gap )()(GGfχχ− can be arbitrarily large. However, as observed in [10], only a few type of graphs G are known to have arbitrarily large gaps between )(Gχ and )(Gfχ. One class of such graphs are the Kneser graphs. It is known [11] that for kn2≥, knkf/)),(nK(=χ. On the other hand, by Lovász Theorem [8], 22)),((+−=knknKχ. This prove that )()(GGfχχ− can be arbitrarily large, if G is Kneser graph. Another class of graphs G are obtained by cone constructions. Suppose ),(EVG= is a graph and is an integer. The -cone 0≥mm)(Gmμ of G is the graph with vertex set }{])1(u[mV∪+× in which ),)(,(jyix is an edge if Exy∈ and 1=−ji or Exy∈ and 0==ji. Moreover, the vertex u is adjacent to ),(mx for all Vx∈. We define )(,GtmK,,21mmμ recursively as ))(G(1m),,,32mmK(,,,21GtmmmKtmμμμ=. Given any graph H, it is known [3,9,12,14] that for for , for 1≥1≥iimHG=0 and )1−(=tGmtGμ, )(tG)ftG(χχ− can be arbitrarily large, although that exact value of the gap )()(tftGGχχ− might be difficult to determine As the kth chromatic number of graphs is a generalization of the chromatic number, it is natural to investigate the kth chromatic numbers of these graphs. The problem of determining the kth chromatic number of Kneser graphs, which is equivalent to the problem of determining existence of homomorphisms among Kneser graphs, has been studied in the literature [2,4,13]. It is known that if rqkk−=', where and 1≥q'0kr<≤ are integers, then rqnknKk2'))','((−≤χ. It was conjectured in [13] that equality holds. The conjecture is verified for 0=ror , but open for other cases. There are also many unsolved problems about this. In this project, we focus on the 1=qkth chromatic number of these graphs, and try to solve some problems. |
| 關鍵字 | 多重著色; k重著色數; 分數著色數; cone graphs; Kneser graphs; multiple colouring; kth chromatic number; fractional chromatic number; cone graphs; Kneser graphs |
| 語言 | |
| 相關連結 |
機構典藏連結 ( http://tkuir.lib.tku.edu.tw:8080/dspace/handle/987654321/46966 ) |