On characterizing Vizing's edge colouring bound

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 i...

Full description

Saved in:
Bibliographic Details
Published in:Journal of graph theory 2012-02, Vol.69 (2), p.160-168
Main Authors: Haxell, Penny, McDonald, Jessica
Format: Article
Language:English
Subjects:
edge colouring
multigraph
Vizing's theorem
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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
ISSN:0364-9024
1097-0118
DOI:10.1002/jgt.20571