摘要
列表著色是將圖 G 上的每一個點 v 著上顏色，所著的顏色必須從 v 所對應的顏色集合 L(v) 中選取。若任意兩個有邊相連的點皆著上不同的顏色，則稱圖 G 為可正當列表著色。當每個點的顏色集合大小皆相同並且圖 G 為可正當列表著色時，去判斷最小可能之點的顏色集合大小即是我們所感興趣的。而此最小可能之點的顏色集合大小稱作圖 G 的列表著色數。在本篇論文中，我們在數種圖形上討論列表著色問題。首先，我們提出了聯合圖形 (cograph) 的列表著色數之上、下界值。事實上，聯合圖形的列表著色數，在此之前是尚未被討論過的。其次，我們集中心力在經過合併運算 (join) 的兩個路徑圖 (path) 上。在此部份，我們提出一些方法，根據這些結果可以對某些正整數 m, n 判定 Pm ۷ Pn 的列表著色數。另一方面，我們依不同的條件，建立兩個平面圖並證明這兩個圖形的列表著色數皆大於 3。
並列摘要
List coloring is to color each vertex v of graph G from its color set L(v). If any two adjacent vertices have different colors, G is colored properly. We are interested in the smallest size of L(v) for every vertex v such that each L(v) has the same size and the graph G is colored properly. Additionally, the smallest size is called the list chromatic number of G. In this thesis, we discuss the list coloring problem for several graphs. First, we give a lower and upper bounds of the list chromatic number for cographs, which was unknown before. Second, we focus on the join operation of two paths, Pm ۷ Pn. There are some results for the list chromatic number of two paths Pm ۷ Pn. Finally, we study this problem on planar graphs. We construct two planar graphs and show that the list chromatic numbers of them are not equal to 3.
參考文獻
[1] N. Alon and M. Tarsi, "Colorings and orientations of graphs," Combinatorica, Vol. 12, pp. 125-134, 1992.
[2] D. Bauer, H. Broersma, and E. Schmeichel, "Toughness in graphs-A survey," Graphs and Combinatorics, Vol. 22, pp. 1-35, 2006.
[3] M. Borowiecki, S. Jendrol, D. Král, and J. Miškuf, "List coloring of Cartesian products of graphs," Discrete Mathematics, Vol. 306, pp. 1955-1958, 2006.
[4] S. Dantas, S. Gravier, and F. Maffray, "Extremal graphs for the list-coloring version of a theorem of Nordhaus and Gaddum," Discrete Applied Mathematics, Vol. 141, pp. 93-101, 2004.
[5] P. Erdös, A. L. Rubin, and H. Taylor, "Choosability in graphs," Congressus Numerantium, Vol. 26, pp. 125-157, 1979.