博碩士論文 942201022 詳細資訊




以作者查詢圖書館館藏 以作者查詢臺灣博碩士 以作者查詢全國書目 勘誤回報 、線上人數:9 、訪客IP:52.87.176.39
姓名 葉政峰(Cheng-Feng Yeh)  查詢紙本館藏   畢業系所 數學系
論文名稱 圖形列表著色
(On list coloring of graphs)
相關論文
★ 圓環面網路上的病毒散播★ 以2D HP 模型對蛋白質摺疊問題之研究
★ On Steiner centers of graphs★ On the Steiner medians of a block graph
★ 秩為5的圖形★ Some results on distance-two labeling of a graph
★ 關於非奇異線圖的樹★ On Minimum Strictly Fundamental Cycle Basis
★ 目標集選擇問題★ 路徑圖與格子圖上的目標集問題
★ 超立方體圖與格子圖上的目標集問題★ 圖形環著色數的若干等價定義
★ 網格圖上有效電阻計算方法的比較★ d 維立方體圖上有效電阻與首達時間的計算方法
檔案 [Endnote RIS 格式]    [Bibtex 格式]    [相關文章]   [文章引用]   [完整記錄]   [館藏目錄]   [檢視]  [下載]
  1. 本電子論文使用權限為同意立即開放。
  2. 已達開放權限電子全文僅授權使用者為學術研究之目的,進行個人非營利性質之檢索、閱讀、列印。
  3. 請遵守中華民國著作權法之相關規定,切勿任意重製、散佈、改作、轉貼、播送,以免觸法。

摘要(中) 在這篇論文中, 我們呈現了一些關於圖形列表著色的結果以及其推廣變形的版本。首先我們在choosability with separation s 上給了一個Nordhaus-Gaddum形式的結果, 推廣了 Erdos, Rubin and Taylor 的一個定理(Congr. Numer. 26 (1979) 125-157)。 再來定義了一個新的圖表參數chg,s (G), 經由討論其上界推廣了Waters
提出的一個定理(J. London Math. Soc. 73 (2006) 565-585)。 在 (Discrete Applied Math. 45 (1993), 277-289) 中, Tesman 提到了如果 Pn 是一個有 n 個點的路徑, 那麼 chs(Pn) = [ 2s(1-1/n) ] + 1, 他的證明能輕易推廣來證明:對於一個有著 n 個點的樹而言,我們有chs(Tn) = [ 2s(1-1/n) ] + 1, 而在此給了一個較簡易且直觀的證明對於chs(Pn) (同時亦對於chs(Tn))。 在(Discrete Appl. Math. 82 (1998) 1-13) 中,Alon and Zaks 證明了 chs(Kn,n) = O(s log n) , 在此篇論文中, 我們給了一個更精確的版本。 對於任意有限圖 G 而言, Waters (J. London Math. Soc. 73 (2006) 565-585) 提出了當 s 趨近無窮大時, cchs(G)/s 極限存在, 並定義此極限為 τ(G)。 最後在此篇論文中
提出了另一種特徵來表示τ(G) , 為 τ(G) = inf{cchs(G)/s : s belongs to N} 。
摘要(英) In this paper we present some results on list coloring and its variants. A Nordhaus-Gaddum type result on choosability with separation s is presented which generalizes a theorem of Erdos, Rubin and Taylor
(Congr. Numer. 26 (1979) 125-157). A new graph parameter chg,s (G) is introduced, and its nontrivial upper bound is provided which generalizes a theorem of Waters (J. London Math. Soc. 73 (2006) 565-585).In (Discrete Applied Math. 45 (1993), 277-289.), Tesman showed that if Pn is a path of n vertices then chs(Pn) = [2s(1 - 1/n)] + 1. He also
remarked that almost the same proof can be easily extended to prove that chs(Tn) = [2s(1 - 1/n)]+1 for a tree Tn of n vertices. Here we give a much shorter and neater proof for Tesman’’s result on chs(Pn) (and hence also on chs(Tn)). In (Discrete Appl. Math. 82 (1998) 1-13)Alon and Zaks proved that chs(Kn,n) = O(s log n). In this paper we present a slightly stronger version of their result. For any finite graph G, Waters (J. London Math. Soc. 73 (2006) 565-585) showed that lim{cchs(G)=s : s tends to infinity} exists, and define this limit as τ(G). In the last part of this paper, we show that there is another characterization of
τ(G), τ(G) = inf {cchs(G)=s : s belongs to N}。
關鍵字(中) ★ 列表著色 關鍵字(英) ★ list coloring
論文目次 中文提要 i
Abstract (in English) ii
誌謝 iii
Contents iv
1 Introduction 1
2 Main results 3
References 10
參考文獻 [1] N. Alon and A. Zaks, T-choosability in graphs, Discrete Appl. Math. 82(1998) 1-13.
[2] P. Erd}os, A. L. Rubin and H. Taylor, Choosability in graph, Congr.Numer. 26 (1979), 125-157.
[3] E. A. Nordhaus and J. W. Gaddum, On complementary graphs, Amer. Math. Monthly 63 (1956), 175-177.
[4] B. A. Tesman, T-colorings, list T-colorings and set T-colorings of graphs, RUTCOR Res. Rept. RRR 57-89, Rutgers University, New Brunswick, NJ (1989).
[5] B. A. Tesman, List T-colorings of graphs, Discrete Applied Math. 45(1993), 277-289.
[6] R. J. Waters, Consecutive list colouring and a new graph invariant, J. London Math. Soc. (2) 73 (2006), 565-585.
指導教授 葉鴻國(Hong-Gwa Yeh) 審核日期 2008-7-7
推文 facebook   plurk   twitter   funp   google   live   udn   HD   myshare   reddit   netvibes   friend   youpush   delicious   baidu   
網路書籤 Google bookmarks   del.icio.us   hemidemi   myshare   

若有論文相關問題,請聯絡國立中央大學圖書館推廣服務組 TEL:(03)422-7151轉57407,或E-mail聯絡  - 隱私權政策聲明