English  |  正體中文  |  简体中文  |  Items with full text/Total items : 79372/79372 (100%)
Visitors : 40061116      Online Users : 430
RC Version 7.0 © Powered By DSPACE, MIT. Enhanced by NTU Library IR team.
Scope Tips:
  • please add "double quotation mark" for query phrases to get precise results
  • please goto advance search for comprehansive author search
  • Adv. Search
    HomeLoginUploadHelpAboutAdminister Goto mobile version


    Please use this identifier to cite or link to this item: http://ir.lib.ncu.edu.tw/handle/987654321/7924


    Title: 圖形列表著色;On list coloring of graphs
    Authors: 葉政峰;Cheng-Feng Yeh
    Contributors: 數學研究所
    Keywords: 列表著色;list coloring
    Date: 2007-06-12
    Issue Date: 2009-09-22 11:09:13 (UTC+8)
    Publisher: 國立中央大學圖書館
    Abstract: 在這篇論文中, 我們呈現了一些關於圖形列表著色的結果以及其推廣變形的版本。首先我們在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}。
    Appears in Collections:[數學研究所] 博碩士論文

    Files in This Item:

    File SizeFormat


    All items in NCUIR are protected by copyright, with all rights reserved.

    社群 sharing

    ::: Copyright National Central University. | 國立中央大學圖書館版權所有 | 收藏本站 | 設為首頁 | 最佳瀏覽畫面: 1024*768 | 建站日期:8-24-2009 :::
    DSpace Software Copyright © 2002-2004  MIT &  Hewlett-Packard  /   Enhanced by   NTU Library IR team Copyright ©   - 隱私權政策聲明