Article ID Journal Published Year Pages File Type
4646972 Discrete Mathematics 2015 5 Pages PDF
Abstract

One consequence of a long-standing conjecture of Goldberg and Seymour about the chromatic index of multigraphs would be the following statement. Suppose GG is a multigraph with maximum degree ΔΔ, such that no vertex subset SS of odd size at most ΔΔ induces more than (Δ+1)(|S|−1)/2(Δ+1)(|S|−1)/2 edges. Then GG has an edge coloring with Δ+1Δ+1 colors. Here we prove a weakened version of this statement.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, ,