| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 9513133 | Discrete Mathematics | 2005 | 6 Pages |
Abstract
We introduce a monotone invariant Ï(G) on graphs and show that it is an upper bound of the chromatic index of graphs. Moreover, there exist polynomial time algorithms for computing Ï(G) and for coloring edges of a multigraph G by Ï(G) colors. This generalizes the classical edge-coloring theorems of Shannon and Vizing.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Martin Kochol, Nad'a KrivoÅáková, Silvia Smejová,