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.