English  |  正體中文  |  简体中文  |  Items with full text/Total items : 52047/87178 (60%)
Visitors : 8697906      Online Users : 217
RC Version 7.0 © Powered By DSPACE, MIT. Enhanced by NTU Library & TKU 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://tkuir.lib.tku.edu.tw:8080/dspace/handle/987654321/105289

    Title: 4-臨界圖的探討
    Other Titles: A study of 4-critical graphs
    Authors: 蔡秀英;Tsai, Hsiu-Ying
    Contributors: 淡江大學中等學校教師在職進修數學教學碩士學位班
    Keywords: 點著色;最少著色數;4-臨界圖;vertex coloring;chromatic number;4-critical graph
    Date: 2015
    Issue Date: 2016-01-22 14:52:24 (UTC+8)
    Abstract: 令G為一個圖,若存在函數C:V(G)⟶{1,2,…,k|k∈Z^+},使得{u,v}∈E(G)時,C(u)≠C(v),我們就稱C為圖G的點著色。若圖G的點著色所需使用的最少顏色數為k,我們稱此圖的著色數(chromatic number)為k,記為X(G)=k。且v為圖G中的任一點,若X(Gv)=k-1,則稱圖G為一個k-臨界圖。在本文中,我們先由7個點的4-臨界圖,找出這些臨界圖的特性,進而我們對所有大於7的奇數n,都可以建構出n個點的4-臨界圖,即n≡1(mod 4)時,可以建構出兩種n個點的4-臨界圖,當n≡3(mod 4)時,可以建構出五種n個點的4-臨界圖。
    Let G be a simple graph. If there exists a function C∶V(G)⟶{1,2,…,k},k∈Z^+, such that C(u)≠C(v), for every {u,v} ∈E(G), the we call C is a vertex coloring of G. If k is the smallest number for the vertex coloring of G, then we call the chromatic number of G is k, denoted by X(G) = k. If the chromatic number of G is k and X(Gv)=k-1, for any vertex v of G, then we call G is a k-critical graph.In this thesis, we construct some 4-critical graphs with odd vertices. First we study those 4-critical graphs with 7 vertices. Then we obtain the following results.(1) When n ≡ 1(mod 4), we obtain two 4-critical graphs with n vertices(2) When n ≡ 3(mod 4), we obtain five 4-critical graphs with n vertices
    Appears in Collections:[數學學系暨研究所] 學位論文

    Files in This Item:

    File Description SizeFormat

    All items in 機構典藏 are protected by copyright, with all rights reserved.

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