English  |  正體中文  |  简体中文  |  全文筆數/總筆數 : 49378/84106 (59%)
造訪人次 : 7375339      線上人數 : 35
RC Version 7.0 © Powered By DSPACE, MIT. Enhanced by NTU Library & TKU Library IR team.
搜尋範圍 查詢小技巧:
  • 您可在西文檢索詞彙前後加上"雙引號",以獲取較精準的檢索結果
  • 若欲以作者姓名搜尋,建議至進階搜尋限定作者欄位,可獲得較完整資料
  • 進階搜尋
    請使用永久網址來引用或連結此文件: http://tkuir.lib.tku.edu.tw:8080/dspace/handle/987654321/46966


    題名: 圖的多重著色數和圖的分數著色數之研究
    其他題名: The Study of the Kth Chromatic Number of Graphs and the Fractional Chromatic Number of Graphs.
    作者: 潘志實
    貢獻者: 淡江大學數學學系
    關鍵詞: 多重著色;k重著色數;分數著色數;cone graphs;Kneser graphs;multiple colouring;kth chromatic number;fractional chromatic number;cone graphs;Kneser graphs
    日期: 2009
    上傳時間: 2010-04-15 15:44:58 (UTC+8)
    摘要: 圖的多重著色是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.
    顯示於類別:[數學學系暨研究所] 研究報告

    文件中的檔案:

    沒有與此文件相關的檔案.

    在機構典藏中所有的資料項目都受到原著作權保護.

    TAIR相關文章

    DSpace Software Copyright © 2002-2004  MIT &  Hewlett-Packard  /   Enhanced by   NTU Library & TKU Library IR teams. Copyright ©   - 回饋