Claim Missing Document
Check
Articles

Found 1 Documents
Search

B-Coloring of Series-Parallel Graphs: Exact Cactus Values, Extremal K2,r Bundles, and the 2Δ Frontier KARRAR OBAYES; Ghadeer OBAYES
EKSAKTA: Berkala Ilmiah Bidang MIPA Vol. 27 No. 05 (2026): Eksakta : Berkala Ilmiah Bidang MIPA (E-ISSN : 2549-7464) In Progress
Publisher : Faculty of Mathematics and Natural Sciences (FMIPA), Universitas Negeri Padang, Indonesia

Show Abstract | Download Original | Original Source | Check in Google Scholar | DOI: 10.24036/eksakta/vol27-iss05/755

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.