Coloring properties of corona products in signed graphs

Abstract

This paper studies coloring and circular coloring of signed graphs. A signed graph is a graph together with a signature that assigns to each edge a sign which is either positive or negative. This paper studies coloring properties of corona products of signed graphs, including vertex corona product, edge corona product, neighbourhood corona product. Assume (G, σ) and (H, τ) are two signed graphs. The vertex corona product, edge corona product and neighborhood corona product of (G, σ) and (H, τ) are denoted by (G ⊙ H, σ ⊙ τ), (G ⋄ H, σ ⋄ τ), and (G ⋆ H, σ ⋆ τ), respectively. We obtain the following upper bounds for their chromatic numbers: χ(G ⊙ H, σ ⊙ τ) ≤ max{χ(G, σ), χ(H, τ) + 2}, χ(G ⋄ H, σ ⋄ τ) ≤ max{χ(G, σ), χ(H, τ) + 4}, and χ(G ⋆ H, σ ⋆ τ) ≤ max{χ(G, σ), χ(H, τ) + 2(Δ(G) + 1)}. Then we study circular coloring of corona products of graphs, and obtained the following upper bounds: χ_c(G ⊙ H, σ ⊙ τ) ≤ max{χ_c(G, σ), χ_c(H, τ) + 4}, χ_c(G ⋄ H, σ ⋄ τ) ≤ max{χ_c(G, σ), χ_c(H, τ) + 8}, and χ_c(G ⋆ H, σ ⋆ τ) ≤ max{χ_c(G, σ), χ_c(H, τ) + 4(Δ(G) + 1)}. We shall show that the upper bound for the circular chromatic number of vertex corona product is attained, by constructing signed Paley graph that achieves this upper bound.