Mathematics – Combinatorics
Scientific paper
2009-06-09
Mathematics
Combinatorics
This paper has been withdrawn by the author. The main open question here was proved in [R. P. Gupta. On the chromatic index an
Scientific paper
An edge colouring of a multigraph can be thought of as a partition of the edges into matchings (a matching meets each vertex at most once). Analogously, an edge cover colouring is a partition of the edges into edge covers (an edge cover meets each vertex at least once). We aim to determine a tight lower bound on the maximum number of parts in an edge cover colouring as a function of the minimum degree delta, which would be an analogue of Shannon's theorem from 1949 on edge-colouring multigraphs. We are able to give a lower bound that is tight except when delta=9 or delta is odd and > 12; in these non-tight cases the best upper and lower bounds differ by one.
No associations
LandOfFree
Edge Cover Colouring Versus Minimum Degree in Multigraphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Edge Cover Colouring Versus Minimum Degree in Multigraphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Edge Cover Colouring Versus Minimum Degree in Multigraphs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-65426