Premium
On characterizing Vizing's edge colouring bound
Author(s) -
Haxell Penny,
McDonald Jessica
Publication year - 2012
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.20571
Subject(s) - combinatorics , mathematics , conjecture , domination analysis , logarithm , bounded function , upper and lower bounds , multiplicity (mathematics) , graph , edge coloring , discrete mathematics , vertex (graph theory) , line graph , graph power , geometry , mathematical analysis
We consider multigraphs G for which equality holds in Vizing's classical edge colouring bound χ′( G )≤Δ + µ, where Δ denotes the maximum degree and µ denotes the maximum edge multiplicity of G . We show that if µ is bounded below by a logarithmic function of Δ, then G attains Vizing's bound if and only if there exists an odd subset S ⊆ V ( G ) with | S |≥3, such that | E [ S ]|>((| S | − 1)/2)(Δ + µ − 1). The famous Goldberg–Seymour conjecture states that this should hold for all µ≥2. We also prove a similar result concerning the edge colouring bound χ′( G )≤Δ + ⌈µ/⌊ g /2⌋⌉, due to Steffen (here g denotes the girth of the underlying graph). Finally we give a general approximation towards the Goldberg‐Seymour conjecture in terms of Δ and µ. © 2011 Wiley Periodicals, Inc. J Graph Theory 69:160‐168, 2012