Abstract
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.
Connections
Explore this paper’s authors, topics and related work.
Building this map preview
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Reviews 0
Write a review
No reviews yet.
Discussion 0
Add a comment
No comments yet.