Incidence coloring of Cartesian product graphs

•We show an upper bound of the incidence coloring number of Cartesian product graphs.•The upper bound is closely related to the number of colors used by the incidences of a vertex.•We solve the incidence coloring conjecture in hypercubes.

For a vertex v∈V(G)v∈V(G), the incidence neighborhood of v  , denoted by IN(v)IN(v), is the set {(v,e):e∈E(G) and v is incident with e}∪{(u,e):e=vu∈E(G)}{(v,e):e∈E(G) and v is incident with e}∪{(u,e):e=vu∈E(G)}. Let Sσ(v)Sσ(v) denote the set of colors assigned to IN(v)IN(v) in G under incidence coloring σ   and s(σ)=max⁡{|Sσ(v)|:v∈V(G)}s(σ)=max⁡{|Sσ(v)|:v∈V(G)}. Let G1□G2G1□G2 denote the Cartesian product of graphs G1G1 and G2G2. Let σiσi be an incidence coloring of graph GiGi and n(σi)n(σi) the number of colors used by σiσi for i∈{1,2}i∈{1,2}. In this paper, we show that if n(σ1)⩾n(σ2)−s(σ2)n(σ1)⩾n(σ2)−s(σ2), then there exists an incidence coloring of G1□G2G1□G2 which uses n(σ1)+s(σ2)n(σ1)+s(σ2) colors; otherwise, there exists an incidence coloring of G1□G2G1□G2 using n(σ2)n(σ2) colors. Based on the result above, we settle the following conjecture in affirmative: For integer p⩾1p⩾1,χi(Qn)={n+1if n=2p−1n+2otherwise, where QnQn is the n  -dimensional hypercube and χi(Qn)χi(Qn) is the incidence coloring number of QnQn.