Paper Info
Title
On Vizing's bound for the chromatic index of a multigraph
Abstract
Two of the basic results on edge coloring are Vizing's Theorem [V.G. Vizing, On an estimate of the chromatic class of a p-graph, Diskret. Analiz. 3 (1964) 25-30 (in Russian); V.G. Vizing, The chromatic class of a multigraph, Kibernetika (Kiev) 3 (1965) 29-39 (in Russian). English translation in Cybernetics 1 32-41], which states that the chromatic index @g^'(G) of a (multi)graph G with maximum degree @D(G) and maximum multiplicity @m(G) satisfies @D(G)@[email protected]^'(G)@[email protected](G)[email protected](G), and Holyer's Theorem [I. Holyer, The NP-completeness of edge-colouring, SIAM J. Comput. 10 (1981) 718-720], which states that the problem of determining the chromatic index of even a simple graph is NP-hard. Hence, a good characterization of those graphs for which Vizing's upper bound is attained seems to be unlikely. On the other hand, Vizing noticed in the first two above-cited references that the upper bound cannot be attained if @D(G)[email protected](G)+1>=5. In this paper we discuss the problem: For which values @D,@m does there exist a graph G satisfying @D(G)[email protected], @m(G)[email protected], and @g^'(G)[email protected][email protected]
Year
DOI
Venue
2009
10.1016/j.disc.2008.04.046
Discrete Mathematics
Keywords
Field
DocType
vizing’s bound,chromatic index,edge coloring,vizing's bound,maximum degree,indexation,upper bound,satisfiability
Edge coloring,Discrete mathematics,Graph,Combinatorics,Multigraph,Chromatic scale,Upper and lower bounds,Multiplicity (mathematics),Degree (graph theory),Mathematics
Journal
Volume
Issue
ISSN
309
15
Discrete Mathematics
Citations 
PageRank 
References 
7
0.59
4
Authors
2
Name
Order
Citations
PageRank
Diego Scheide1365.21
Michael Stiebitz220730.08