A refinement of Vizing's theorem

DOI10.1016/S0012-365X(99)00361-1MaRDI QIDQ1978167zbMATH OpenOpenAlexFDO

Authors Eckhard Steffen

Publication date 3 December 2000

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0012-365x(99)00361-1

zbMATH Keywords

chromatic indexedge colouringgrithmultigraphVizing's theorem

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Review text

Vizing's theorem [\textit{V. G. Vizing}, The chromatic class of a multigraph, Cybernetics 1, 32-41 (1965; see also Zbl 0166.19601)] states for any multigraph \(M\) (without loops) with maximum vertex-degree \(\Delta(M)\) and maximum edge-multiplicity \(\mu(M)\), its chromatic index \(\chi'(M)\) satisfies the inequality \(\chi'(M)\leq\Delta(M)+ \mu(M)\). In the paper under review, Vizing's theorem is refined to the inequality \[ \chi'(M)\leq \Delta(M)+ \Biggl\lceil{\mu(M)\over \lfloor g/2\rfloor}\Biggr\rceil, \] where \(g\) is the grith of \(M\) and \(\lfloor x\rfloor\) and \(\lceil x\rceil\) are, respectively, the floor and ceiling of \(x\).

Recommendations

• A generalization of edge-coloring in graphs
• A short proof for a generalization of Vizing's theorem
• On Vizing's bound for the chromatic index of a multigraph
• On characterizing Vizing's edge colouring bound
• Achieving maximum chromatic index in multigraphs

Cited in

(7)

• Refining Rossberg's theorem
• Maximum -edge-colorable subgraphs of class II graphs
• On characterizing Vizing's edge colouring bound
• scientific article; zbMATH DE number 7039406 (Why is no real title available?)
• A short proof for a generalization of Vizing's theorem
• Refinement of the theorem of Vahlen
• Set-coloring of edges and multigraph Ramsey numbers

This page was built for publication: A refinement of Vizing's theorem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1978167)