On a theorem of Goldberg

Let G be a multigraph with maximum degree Δ and odd‐girth g o ≥3. Goldberg [J Graph Theory 8 (1984), 123–137] has shown thatand this bound is easily seen to be tight—for example, ( g o ) C   g   oachieves the bound. However, in light of the famous Seymour–Goldberg Conjecture, which postulates that(where ρ( G ) is the maximum of 2| E [ S ]|/(| S | − 1) over all odd‐subsets S of V ( G ) of size at least 3), Goldberg's bound may still have room for refinement. Here, we proceed in this direction, proving thatTo complement this result, we provide a characterization of those multigraphs with χ′>Δ + 1 + ((Δ − 3)/( g o + 3)). All of our proofs provide efficient algorithms. Copyright © 2010 John Wiley & Sons, Ltd. 68:8‐21, 2011