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

目錄	I
圖目錄	II
第一章 簡介	1
第二章 預備知識及輔助定理	3
第三章 4-臨界圖的探討	10
第一節 圖F3的推廣	12
第二節 圖F4的推廣	15
第三節 圖F5的推廣	19
第四節 圖F6的推廣	23
第五節 圖F7的推廣	27
第四章 結論及展望	32
參考文獻	33
圖目錄
第二章
圖2. 1  G	3
圖2. 2  G,H,R	3
圖2. 3  G	4
圖2. 4  G	4
圖2. 5  G	6
圖2. 6  G,H	6
圖2. 7  G,H	7
第三章
圖3. 1  7點4-臨界圖	11
圖3. 2  G1	12
圖3. 3  G1a1	13
圖3. 4  G1a2	13
圖3. 5  G1a3	13
圖3. 6  G1a4	13
圖3. 7  G1 1	13
圖3. 8  G	14
圖3. 9  H	15
圖3. 10  G2	16
圖3. 11  G2a1	17
圖3. 12  G2a2	17
圖3. 13  G2a3	17
圖3. 14  G2a4	17
圖3. 15  G2a5	17
圖3. 16  G2 1	17
圖3. 17  G	18
圖3. 18  G3	20
圖3. 19  G3a1	21
圖3. 20  G3a2	21
圖3. 21  G3a3	21
圖3. 22  G3a4	21
圖3. 23  G3 1	21
圖3. 24  G3 2	21
圖3. 25  G	22
圖3. 26  H	23
圖3. 27  G4	24
圖3. 28  G4a1	25
圖3. 29  G4a2	25
圖3. 30  G4a3	25
圖3. 31  G4a4	25
圖3. 32  G4a5	25
圖3. 33  G4 1	25
圖3. 34  G	26
圖3. 35  H	27
圖3. 36  G5	28
圖3. 37  G5a1	29
圖3. 38  G5a2	29
圖3. 39  G5a3	29
圖3. 40  G5a4	29
圖3. 41  G5a5	29
圖3. 42  G5 1	29
圖3. 43  G	30

1.	J. I. Brown, A vertical critical graph without critical edges, Discrete Mathematics 102 (1992) 99-101
2.	G. A. Dirac, Problem 7 conjectured in 1970 , Graph Theory in Memory of G.A. Dirac, Ann. Discrete Math. 41 (1989), pp. 516
3.	P. Erdo˝s, On some aspects of my work with Gabriel Dirac. In: L. D. Andersen, I. T. Jakobsen, C. Tomassen, B. Toft, and P. D. Vestergaard (editors), Graph Theory in Memory of G. A. Dirac, Vol. 41 of Ann Discrete Math, NorthHolland, (1989), pp. 111–116
4.	R. Jensen and B. Toft, Graph coloring problems, John Wiley & Sons. Inc.,  pp.109-112,1995
5.	郭崇人, 點著色臨界圖的研究, 淡江大學數學系碩士論文, 2003