4-臨界圖的探討

機構典藏 > College of Sciences > Graduate Institute & Department of Mathematics > Thesis > Item 987654321/105289

Please use this identifier to cite or link to this item: https://tkuir.lib.tku.edu.tw/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:	令Ｇ為一個圖，若存在函數C:V(G)⟶{1,2,…,k\|k∈Z^+}，使得{u,v}∈E(G)時，C(u)≠C(v)，我們就稱C為圖Ｇ的點著色。若圖Ｇ的點著色所需使用的最少顏色數為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 Ｇ 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 Ｇ. 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:	[Graduate Institute & Department of Mathematics] Thesis

Files in This Item:

File	Description	Size	Format
index.html		0Kb	HTML	379	View/Open

Loading...