簡易檢索 / 詳目顯示

回結果列表
研究生： 王博賢
論文名稱： 平面圖的平方著色數
The Chromatic Number of the Square of a Planar Graph
指導教授： 郭君逸
學位類別： 碩士
Master
系所名稱： 數學系
Department of Mathematics
論文出版年： 2014
畢業學年度： 102
語文別： 中文
論文頁數： 41
中文關鍵詞： 平面圖 、著色數 、圖的標號 、放電法
英文關鍵詞： planar graph, chromatic number, labeling of a graph, discharging
論文種類： 學術論文
相關次數： 點閱：172  下載：23 
分享至:
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報

    • 放電法(Discharging Method)最早在1977年，Appel使用來證明對於任何平面圖G，χ(G)≤4 (即四色定理)。而Heuvel等人在1999年，使用放電法證明了χ(G^2 )≤2"Δ"+25。在我們這篇論文中，將此上界降低至2"Δ"+10，加上涵蓋了前人的一些結果，我們並將這個結果推廣到λ(G;p,q)≤(4q-2)"Δ"+10p+8q-9。

    Discharging method was proposed in 1977 by Appel and Haken, he used it to prove that for any planar graph G, χ(G)≤4, that is well-known 4-Color Theorem. Heuvel et al. used discharging method to prove χ(G^2 )≤2"Δ"+25 in 1999. In this paper, we reduce this upper bound to 2"Δ"+10 and also generalize the result to λ(G;p,q)≤(4q-2)"Δ"+10p+8q-9.

    目錄 ii 摘要 iii Abstract iv 一、導論 1 二、定理1.2的證明 3 三、放電法 6 四、結論 38 Refernece 40

    [1] G. Agnarsson and M. M. Halldo´rsson, Coloring Powers of planar graphs. Preprint (2000).
    [2] K. Appel and W. Haken, Every planar map is four colourable. Part I:Discharging, Illinois J Math 21 (1977), 429–490.
    [3] K. Appel, W. Haken, and J. Koch, Every planar map is four colourable. Part II: Reducibility, Illinois J Math 21 (1977), 491–567.
    [4] O. V. Borodin, H. J. Broersma, A. Glebov, and J. van den Heuvel, Stars and bunches in planar graphs. Part I: Triangulations. CDAM Research Report Series 2002-04 (2002). Original Russian version. In: Diskretn Anal Issled Oper Ser 1 8, no. 2 (2001), 15–39.
    [5] O. V. Borodin, H. J. Broersma, A. Glebov, and J. van den Heuvel, Stars and bunches in planar graphs. Part II: General planar graphs and colourings. CDAM Research Report Series 2002-05 (2002). Original Russian version. In: Diskretn Anal Issled Oper Ser 1 8, no. 4 (2001), 9–33.
    [6] P. J. Heawood, Map colour theorem, Quart J Pure Appl Math 24 (1890), 332–338.
    [7] J. van den Heuvel, and S. McGuinness, Colouring the square of a planar graph J. Graph Theory, 42 (2003), pp. 110–124.
    [8] T. R. Jensen and B. Toft, Graph coloring problems, John-Wiley & Sons, New York (1995).
    [9] T. K. Jonas, Graph coloring analogues with a condition at distance two: L(2,1)-labellings and list λ-labellings. Ph.D. Thesis, University of South Carolina (1993).
    [10] M. Molloy and M. R. Salavatipour, A bound on the chromatic number of the square of a planar graph. Preprint, University of Toronto (2002).
    [11] N. Robertson, D. Sanders, P. Seymour, and R. Thomas, The four-colour theorem, J Comb Th 70 (1997), 2–44.
    [12] G. Wegner, Graphs with given diameter and a colouring problem. Preprint, University of Dortmund (1977).
    [13] S.A. Wong, Colouring graphs with respect to distance, M.Sc. Thesis, Department of Combinatorics and Optimization, University of Waterloo, 1996.

    QR CODE