B-Coloring of Series-Parallel Graphs: Exact Cactus Values, Extremal K2,r Bundles, and the 2Δ Frontier

Abstract

B-coloring strengthens proper edge-coloring by requiring every 4-cycle to be rainbow, so conflicts arise not only at common endpoints but also between opposite cycle edges. Existing planar bounds settle the twice-maximum-degree threshold in several cases, but not throughout the series-parallel class. We study this gap by combining structural arguments with exact verification through the B-conflict graph. For connected cactus graphs, we determine the B-chromatic index exactly and obtain a linear-time optimal coloring procedure. For K2,r, we prove qB(K2,r)=2r=2Δ, showing that the factor two cannot be reduced in a universal degree bound. Minimal-counterexample reductions then confine any unresolved obstruction to non-bipartite, low-degree series-parallel graphs in which degree-two vertices lie on interacting 4-cycles. Exact DSATUR and integer-programming models provide independently checkable finite certificates, while a separate feasibility procedure tests the 2Δ threshold on individual instances without replacing proof. The analysis isolates external 4-cycle coupling as the main structural difficulty that remains.