Incidence coloring on hypercubes

Let χi(G)χi(G) and Δ(G)Δ(G) denote the incidence coloring number and the maximum degree of a graph G  , respectively. An easy observation shows that χi(G)⩾Δ(G)+1χi(G)⩾Δ(G)+1. In this paper, we consider incidence coloring number on hypercubes QnQn. Based on the technique of Hamming codes, we present algorithms to obtain upper bounds of χi(Qn)χi(Qn) for n   in certain forms of integers. Let p,qp,q be positive integers. We show that (1) χi(Qn)=n+1χi(Qn)=n+1 if n=2p−1n=2p−1 for p⩾1p⩾1; (2) χi(Qn)=n+2χi(Qn)=n+2 if the following conditions hold: (i) n=2p−2n=2p−2 for p⩾2p⩾2; (ii) n=2p+2q−2n=2p+2q−2 for p,q⩾1p,q⩾1; (iii) n=2p+2q−3n=2p+2q−3 for p,q⩾2p,q⩾2; and (3) χi(Qn)⩾n+2χi(Qn)⩾n+2 otherwise.