On characterizing Vizing's edge colouring bound |
| |
Authors: | Penny Haxell Jessica McDonald |
| |
Affiliation: | 1. Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Ont., Canada N2L 3GL;2. Department of Mathematics, Simon Fraser University, 8888 University Drive, Burnaby, BC, Canada V5A 1S6 |
| |
Abstract: | 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 |
| |
Keywords: | multigraph edge colouring Vizing's theorem |
|
|