کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
428501 | 686785 | 2015 | 4 صفحه PDF | دانلود رایگان |
• 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.
Journal: Information Processing Letters - Volume 115, Issue 10, October 2015, Pages 765–768