Eksakta : Berkala Ilmiah Bidang MIPA
Vol. 27 No. 05 (2026): Eksakta : Berkala Ilmiah Bidang MIPA (E-ISSN : 2549-7464) In Progress

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

KARRAR OBAYES (Department of Computer Information Systems, University of Al-Qadisiyah, Al Diwaniyah, Iraq)
Ghadeer OBAYES (General Directorate of Education in Al-Qadisiyah, Al Diwaniyah, Iraq)



Article Info

Publish Date
30 Oct 2026

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.

Copyrights © 2026






Journal Info

Abbrev

eksakta

Publisher

Subject

Agriculture, Biological Sciences & Forestry Astronomy Biochemistry, Genetics & Molecular Biology Chemical Engineering, Chemistry & Bioengineering Chemistry Civil Engineering, Building, Construction & Architecture Computer Science & IT Energy Engineering Environmental Science Materials Science & Nanotechnology Mathematics Mechanical Engineering

Description

Eksakta : Berkala Ilmiah Bidang MIPA (E-ISSN : 2549-7464) is an open access journal and peer-reviewed that publishes either original article or reviews. The journal is dedicated towards dissemination of knowledge related to the advancement in scientific research. The prestigious interdisciplinary ...