摘要本文解决了Halin图的点色数问题,并给出了一个可在线性时间内对Halin图进行点着色的算法。In this paper, we determine the vertex chromatic number of Halin graphs, and then give a linear time algorithm for colouring of Halin graphs.
5HALIN R. Studies on minimally n-connected graphs [J]. Combinatorial Mathematics and its Applications, Academic Press, London, 1971, 129--136.
6CORNUEJOLS G, NADDEF D, PULLEYBLANK W R. Halin grapha and the travelling salesman problem [J]. Mathematical Programming, 1983, 26: 287--294.
7HORTON S B, PARKER R G. On Halin subgraphs and supergraphs [J]. Discrete Applied Mathematics, 1995, 56: 19--35.
8LI H X, ZHANG Z F, ZHANG J X. On the colouring of Halin graphs [J]. J. Shanghai Inst. of Railway Tech. , 1994, 15(1): 19--24.
9ZHANG Zhong-fu, LIU Lin-zhong, WANG Jian-fang et al. A note on the total chromatic number of Halin graphs with maximum degree 4 [J]. Appl. Math. Lett. , 1998, 11(5): 23--27. (in Chinese).
10BONDY J A, MURTY U S R. Graph Theory with Applications [M]. Londons Macmillan Press,1976.
