| 摘要: | 令Ｇ為一個圖，若存在函數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 |
