在這篇論文中，我們從房間配置的角度探討與解決點著色問題。在房間配置中，點與點之間的著色情形對應到一張「旅館表(Hotel table)」，每個點就稱之為一個「顧客(Customer)」。表格的行稱為「樓層(Stair)」，一行就代表圖中一個連通子圖(Connected sub-graph)。表格的列稱為「房間(Room)」。一列代表一種顏色。圖中顏色相同的點就放在同一列。
　　旅館表可以看到較具體的點與點互動情形，而所使用的房間數量即是著色問題所使用的顏色數。因此如何找到最小點著色數的問題，可直接相等於如何求得最少的房間數。本文的前半段簡介點著色問題，並且討論旅館表的特性。接著以透過顧客與顧客之間的「溝通(Communication)」來盡量減少房間數完成配置。我們所提出的方法為「房間配置演算法(Room-allocation algorithm)」。其中包含了以鄰居關係順序配置房間的「基本法」、「隨機法」、「剝殼法」，以及以顧客順序配置房間的「三合院法」。前三種方法可以計算任意圖的著色解，而三合院法只能判斷是否為3 可著色。論文最後測試一些隨機產生的圖，討論並分析測試結果。
　　令N和M為圖G的點數量與邊數量、Δ(G)為圖G所有點中相鄰點數量最多的相鄰點數量、stepmax為隨機法中設定的最大迭代次數，則「基本法」、「隨機法」、「剝殼法」的時間複雜度依序為O(M)+O(Δ(G))、O(M)+O(stepmax·(Δ(G))^2)、O(M)+O((Δ(G))^3)，對於二分圖保證能得到兩種顏色的著色，但對於最小著色數大於2的圖形，著色數有時比貪婪法好，有時則非；「三合院法」的時間複雜度為O(N^2)至O(N^3·2^N)，根據Ratio=MN和G的最小著色數的不同決定複雜度，當圖的最小著色數大於3，「三合院法」只需要小於O(N^2) 的複雜度判斷G不為3可著色；令min(TQH)為三合院法的最小分界值、max(TQH)為三合院法的最大分界值，當圖的最小著色數為3且Ratio < min(TQH)，則「三合院法」需要O(N^3)的複雜度；當圖的最小著色數為3且Ratio>max(TQH)，則「三合院法」需要O(N^2)的複雜度；當圖的最小著色數為3且min(TQH)≤Ratio≤max(TQH)，則「三合院法」需要O(N^3·2^N)的複雜度。當圖的最小著色數為2，「三合院法」會得到一個不大於3的著色解，但不保證得到著色數為2的解，當圖的最小著色數為3，「三合院法」保證得到一個著色數為3的解。

In this thesis, we solved the vertex coloring problem by constructing a “hotel table” which is corresponding to a colored graph. In the hotel table, a column is called a “stair”. The stair represented the connected sub-graph in the graph. A row is called a “room”. The room represented the color of the vertex in the graph. A vertex is considered as a “customer” in the hotel.
First, we introduced the vertex coloring problem, and discussed the properties of the hotel table. Then we define the “communication” between customers to reduce the number of the rooms as possible as we can. We proposed the “room-allocation algorithm”, which includes four methods, “basic method”, “random method”, “shell method”, and the “quadrangle house method”. The first three methods are based on the order of the edges while the last is based on the order of vertices.
Let N be the number of nodes in the graph G, M be the number of edges in the graph G, degree(v) be the the number of graph edges which touch node v, Δ(G) be the maximum degree, stepmax be the maximum iteration number set in random method. “Basic method”, “random method”, “shell method” had average complexity O(M)+O(Δ(G)), O(M)+O(stepmax•(Δ(G))^2), and O(M)+O((Δ(G))^3), respectively. These algorithm would get solution with two colors for bipartite graph. “Quadrangle house method” had complexity O(N^2) to O(N^3•2^N) which depends on ratio (M/N) and chromatic number of G.

[1] Michael R Garey, David S. Johnson, and Larry Stockmeyer. Some simplified npcomplete graph problems. Theoretical computer science, 1(3):237–267, 1976.
[2] Preston Briggs. Register allocation via graph coloring. PhD thesis, Rice University,1992.
[3] Armen S Asratian, Tristan MJ Denley, and Roland Häggkvist. Bipartite graphs and their applications, volume 131. Cambridge University Press, 1998.
[4] D. J. A. Welsh and M. B. Powell. An upper bound for the chromatic number of a graph and its application to timetabling problems. The Computer Journal, 10(1): 85, 1967.
[5] Rowland Leonard Brooks. On colouring the nodes of a network. In Mathematical Proceedings of the Cambridge Philosophical Society, volume 37, pages 194–197.　Cambridge University Press, 1941.
[6] Daniel Brélaz. New methods to color the vertices of a graph. Communications of the ACM, 22(4):251–256, 1979.
[7] Jeremy P. Spinrad and Gopalakrishnan Vijayan. Worst case analysis of a graph coloring algorithm. Discrete Applied Mathematics, 12(1):89 – 92, 1985. 83
[8] Andreas Björklund, Thore Husfeldt, and Mikko　Koivisto. Set partitioning via inclusion-exclusion. SIAM Journal on Computing, 39(2):546–563, 2009.
[9] Richard Beigel and David Eppstein. 3-coloring in time o(1.3289^n). Journal of Algorithms, 54(2):168–204, 2005.
[10] Venkatesan Guruswami and Sanjeev Khanna. On the hardness of 4-coloring a 3-collorable graph. In Computational Complexity, 2000. Proceedings. 15th Annual IEEE Conference on, pages 188–197. IEEE, 2000.