2025/04/17 by Xiaolan Hu, Kuffner Luis, Hu, Xiaolan +7 · 1 citation
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.2504.12620
openalex publication_date 2025/04/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A signed graph is a pair (G,σ), where G is a graph and σ: E(G)→ \-, +\, called signature, is an assignment of signs to the edges. Given a signed graph (G,σ) with no negative loops, a balanced (p,q)-coloring of (G,σ) is an assignment f of q colors to each vertex from a pool of p colors such that each color class induces a balanced subgraph, i.e., no negative cycles. Let (K4,-) be the signed graph on K4 with all edges being negative. In this work, we show that every signed (simple) subcubic graph admits a balanced (5,3)-coloring except for (K4,-) and signed graphs switching equivalent to it. For this particular signed graph the best balanced colorings are (2p,p)-colorings.