著色問題在過去廣受重視，許多相關的問題被研究與探討。而這些論文探討的方向，最主要的就是如何透過好的演算法，來降低著色時所需的最少顏色數。而所應用的圖形除了cycle外，還包括hypercube、complete graph…等。
區域性的著色法在過去的研究中，並不被十分熱烈的討論，只有在較為單調簡單的圖形中，如cycle，被提出解法。因此，區域性的著色法尚有很大的研究空間與價值。本論文就從特殊圖形（3-regular Cycle圖形）中去探討它的區域著色法。選擇3-regular Cycle圖形的原因是，它具有類似環狀圖的性質，一樣可以從頭到尾圍成一圈。
在3-regular Cycle圖形中，我們可以發現它是由許多四邊形所組成，因此，我們只須計算出n種顏色最多能造出幾種不同的四邊形，再將這些四邊形依照規則加以排列，使成這些四邊形成為一大串列即可。最後，我們證明任意大小的3-regular Cycle圖形均可經由我們所提出的方法來著色。

The coloring problem and many related problems are very popular problems. A lot of papers are concerned with finding good algorithm to reduce the number of colors. There are also some papers discussing this problem on some special graphs which include cycles, hypercubes, complete graphs, etc..
Local coloring problem rarely discussed in the past. In this thesis, we discuss the local coloring problem for a special graph called 3-regular cycles. A 3-regular cycle graph resembles a cycle which the degree of every vertex is three. In this thesis, we shall propose an efficient algorithm for solving this problem.
A 3-regular cycle graph is formed by many quadrilaterals. The coloring problem of this graph can be viewed as the local coloring problem of quadrilaterals. At first, we try to construct a 3-regular cycle in which contains as many quadrilaterals as possible. Note that each quadrilateral is with different colors. Finally, we will show that, by using our method, we can construct a 3-regular cycle with any length less then +4 +6 +2 , where r is the number of colors.

[1] M. Albertson, K. Collins, Symmetry breaking in graph. Electronic Journal of Combinatorics 3（1996）.
[2] N. Alon, C.J.H. McDiarmid, B.A. Reed, Acyclic coloring of graphs, Random Structures and Algorithms 2（1991）277-288.
[3] L. Babai, P. Erdős, S. Selkow, Random graph isomorphism, SIAM Journal on Computing 3（1980）628-635.
[4] D.G.. Beane, N.L. Biggs and B.J. Wilson, The growth rate of the harmonious chromatic number. Journal of Graph Theory 13（1989）291-298.
[5] Bill Bogstad, Lenore J. Cowen, The distinguishing number of the hypercube. Discrete Mathematics 283（2004）29-35.
[6] O.V. Borodin, On acyclic colorings of planar graphs, Discrete Mathematics 25（1979）211-236.
[7] O.V. Borodin, A.V. Kostochka, J. Nešetřil, A. Raspaud, E. Sopena, On the maximum average degree and the oriented chromatic number of a graph, Discrete Mathematics 206（1999）77-89.
[8] O.V. Borodin, A.V. Kostochka, D.R. Woodall, Acyclic coloring of planar graphs with large girth, J. London Math. Soc. 60（1999）344-352.
[9] O.V. Borodin, A.V. Kostochka, A. Raspaud, E. Sopena, Acyclic coloring of 1-planar graphs, Diskretnyi Analiz i Issledovanie Operacii, Series 1 6（4）（1999）20-35.
[10] O.V. Borodin, D.G. Fon-Der Flass, A.V. Kostochka, A. Raspaud, E. Sopena, Acyclic list 7-coloring of planar graphs, J. Graph Theory 40（2）（2002）83-90.
[11] C.T. Chen*, L.J. Cowen, On the local distinguish numbers of cycles. Discrete Mathematic 196（1999）97-108.
[12] K.B. Chilakamarri, On the chromatic number of rational five-space, Aequationes Mathematicae 39（2-3）（1990）146-148.
[13] Chu-Yen Chou, Weifan Wang, Xuding Zhu, Relaxed game chromatic number of graphs, Discrete Mathematics 262（2003）89-98.
[14] C.J. Colbourn, The complexity of completing partial Latin squares, Discrete Applied Mathematics 8（1）（1984）25-30.
[15] P. Erdős, M. Simonovits, On the chromatic number of geometric graphs, Ars Combinatoria 9（1980）229-246.
[16] Guillaume Fertin, E. Godard, A. Raspaud, Minimum feedback vertex set and acyclic coloring, Information Processing Letters 84（2002）131-139.
[17] Guillaume Fertin, André Raspaud, Arup Roychowdhury, On the oriented chromatic number of grids, Information Processing Letters 85（2003）261-266.
[18] O. Frank, F. Harary and M. Plantholt, The line-distinguish chromatic number of a graph, Ars Combinatoria 14（1982）241-252.
[19] Krzysztof Giaro, Marek Kubale, Edge-chromatic sum of trees and bounded cyclicity graphs, Information Processing Letters 75（2000）65-69.
[20] B. Grünbaum, Acyclic colorings of planar graphs, Israel Journal Mathematics 14（1973）390-408.
[21] I. Hoffman, A. Soifer, Almost chromatic number of the plane, Geombinatorics 3（2）（1993）38-40.
[22] J. Hopcroft and M.S. Krishnamoorthy, On the harmonious colorings of graphs, SIAM Journal Discrtet Mathematics 4（1983）306-311.
[23] A.V. Kostochka, Upper bounds of chromatic functions of graphs, Ph.D. Thesis, Novosibirsk, 1978（in Russian）.
[24] J. Kratochvíl, Precoloring extension with fixed color bound, Acta Math. Univ. Comenian. 62（2）（1993）139-153.
[25] S.-M. Lee and J. Mitchem, An upper bound for the harmonious chromatic number of a graph, Journal of Graph Theory 11（1987）565-567.
[26] L. Lovász, Self dual polytopes and the chromatic number of distance graphs on the sphere, Acta Scientiarum Mathematicarum 45（1983）317-323.
[27] Zhikang Lu, On an upper bound for the harmonious chromatic number of a graph, j. Graph Theory 15（1991）345-347.
[28] Zhikang Lu, The harmonious chromatic number of a complete binary and trinary tree, Discrete Mathematic 118（1993）165-172.
[29] Zhikang Lu, The exact value of the harmonious chromatic number of a complete binary tree, Discrete Mathematics 172（1997）93-101.
[30] D. Marx, List edge multicoloring in graphs with few cycles, Information Processing Letters 89（2004）85-90.
[31] D. Marx, The complexity of tree multicolorings, in: Mathematical Foundations of Computer science 2002（Warsaw-Otwock）,Springer, Berlin, 2002, pp. 532-542.
[32] Z. Miller and D. Pritikin, The harmonious coloring number of a graph, Congressus Numerantium 63（1988）213-228.
[33] J. Mitchem, On the harmonious chromatic number of a graph, Discrete Mathematics 74（1989）151-157.
[34] Shin-ichi Nakayama, Shigeru Masuyama, A parallel algorithm for solving the coloring problem on trapezoid graphs, Information Processing Letters 62（1997）323-327.
[35] Oren Nechushtan, On the space chromatic number, Discrete Mathematics 256（2002）499-507.
[36] J. Nešetřil, A. Raspaud, E. Sopeana, Colorings and girth of oriented planar graphs, Discrete Mathematics 165-166（1997）519-530.
[37] A. Raspaud, E. Sopena, Good and semi-strong colorings of oriented planar graphs, Information Processing Letters 51（1994）171-174.
[38] San Skulrattanakulchai, Acyclic colorings of subcubic graphs, Information Processing Letters 92（2004）161-167.
[39] San Skulrattanakulchai, 4-edge-coloring graphs of maximum degree 3 in linear time, Information Processing Letters 81（2002）191-195.
[40] E. Sopena, The chromatic number of oriented graphs, Journal of Graph Theory 25（1997）191-205.