Premium
On a theorem of Goldberg
Author(s) -
McDonald J. M.
Publication year - 2011
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20537
Subject(s) - multigraph , combinatorics , mathematics , complement (music) , mathematical proof , conjecture , upper and lower bounds , characterization (materials science) , graph , extremal graph theory , discrete mathematics , line graph , voltage graph , physics , geometry , complementation , gene , mathematical analysis , biochemistry , chemistry , phenotype , optics
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