International Journal of Mathematics and Mathematical Sciences
Volume 2005 (2005), Issue 5, Pages 803-813
doi:10.1155/IJMMS.2005.803
The incidence chromatic number of some graph
1College of Information & Engineering, Shandong University of Science and Technology, Shandong, Qingdao 266510, China
2School of Professional Technology, Xuzhou Normal University, Jiangsu, Xuzhou 221011, China
Received 1 April 2003; Revised 5 December 2003
Copyright © 2005 Liu Xikui and Li Yan. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
Abstract
The concept of the incidence chromatic number of a graph was introduced by Brualdi and Massey (1993). They conjectured that every graph G can be incidence colored with Δ(G)+2 colors. In this paper, we calculate the incidence chromatic numbers of the complete k-partite graphs and give the incidence chromatic number of three infinite families of
graphs.