International Journal of Mathematics and Mathematical Sciences
Volume 2005 (2005), Issue 5, Pages 803-813

The incidence chromatic number of some graph

Liu Xikui1,2 and Li Yan1

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.


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.