The list chromatic numbers of some planar graphs
Tóm tắt
In this paper the choosability of outerplanar graphs, 1-tree and strong 1-outerplanar graphs have been described completely. A precise upper bound of the list chromatic number of 1-outerplanar graphs is given, and that every 1-outerplanar graph with girth at least 4 is 3-choosable is proved.
Tài liệu tham khảo
Bondy, J. A., Murty, U. S. R., Graph Theory with Applications,, The Macmillian Press Limit, new York, 1976.
Vizing, V. G., Coloring the vertices of a graph in prescribed colors, Diskret Analiz, 1976, 29: 3–10. (in Russian)
Erdös, P., Rubin, A. L. and Taylor, H, Choosability in graphs, Congr. Numer, 1980, 26: 122–157.
Alon, N., Tarsi, M., Colorings and orientations of graphs, Combinatorica, 1992, 12 (2): 125–134.
Thomassen, C., Every lanar graph is 5-choosable, J. Combin. Theory Ser. B, 1994, 62 (1): 180–181.
Voigt, M., List colourings of planar graphs, Discrete Math., 1993, 120: 215–219.
Thomassen, C., 3-list coloring planar graphs of girth 5, J. Combin. Theory Ser. B, 1995, 64 (1): 101–107.
Wang Weifan, Equitable colorings, and total colorings of graphs. [Doctoral Thesis], Najing: Nanjing University, 1997.
Tian Feng and Ma Zhongfan, Graphs and Network Flows, Science Press, Beijing, 1987.