Abstract | ||
---|---|---|
Let f(Δ, μ) = max {χ′(G) | Δ (G) = Δ, μ(G) = μ} where χ′(G), Δ(G) and μ(G) denote the the chromatic index, the maximum degree and the maximum multiplicity of the multigraph G, respectively. If Δ < 2μ, then Shannon’s bound implies that the gap between f(Δ, μ) and Vizing’s bound Δ + μ can be arbitrarily large. In this note, we prove that this is also the case for Δ ≥ 2μ (see Theorem 4). |
Year | DOI | Venue |
---|---|---|
2012 | 10.1007/s00373-011-1068-4 | Graphs and Combinatorics |
Keywords | Field | DocType |
Chromatic index, Vizing’s bound | Topology,Edge coloring,Discrete mathematics,Combinatorics,Multigraph,Multiplicity (mathematics),Degree (graph theory),Mathematics,Arbitrarily large | Journal |
Volume | Issue | ISSN |
28 | 5 | 1435-5914 |
Citations | PageRank | References |
0 | 0.34 | 4 |
Authors | ||
2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Diego Scheide | 1 | 36 | 5.21 |
Michael Stiebitz | 2 | 207 | 30.08 |