On a theorem of Goldberg
Jessica M. McDonald · Journal of Graph Theory · 2011
Let G be a multigraph with maximum degree Δ and odd-girth go≥3. Goldberg [J Graph Theory 8 (1984), 123–137] has shown that and this bound is easily seen to be tight—for example, (go)C achieves 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 that To complement this result, we provide a characterization of those multigraphs with χ′>Δ + 1 + ((Δ − 3)/(go + 3)). All of our proofs provide efficient algorithms. Copyright © 2010 John Wiley & Sons, Ltd. 68:8-21, 2011