2016/03/31 by Sandip Das, Das, Sandip, Soumen Nandi +5
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Graph theory and applications
paper · pdf · doi:10.48550/arxiv.1603.09557
openalex publication_date 2016/03/31 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A signed graph (G, Σ) is a graph positive and negative (Σ denotes the set of negative edges). To re-sign a vertex v of a signed graph (G, Σ) is to switch the signs of the edges incident to v. If one can obtain (G, Σ') by re-signing some vertices of (G, Σ), then (G, Σ) ≡ (G, Σ'). A signed graphs (G, Σ) admits an homomorphism to (H, Λ) if there is a sign preserving vertex mapping from (G,Σ') to (H, Λ) for some (G, Σ) ≡ (G, Σ'). The signed chromatic number χs( (G, Σ)) of the signed graph (G, Σ) is the minimum order (number of vertices) of a signed graph (H, Λ) such that (G, Σ) admits a homomorphism to (H, Λ). For a family F of signed graphs χs(F) = max(G,Σ) ∈ F χs( (G, Σ)). We prove 2Δ/2-1 ≤ χs(GΔ) ≤ (Δ-1)2. 2(Δ-1) +2 for all Δ≥ 3 where GΔ is the family of connected signed graphs with maximum degree Δ. \endabstract