Beyond the Shannon's Bound

Michał Farnik, Łukasz Kowalik, Arkadiusz Socała

Let $G=(V,E)$ be a multigraph of maximum degree $\Delta$. The edges of $G$ can be colored with at most $\frac{3}{2}\Delta$ colors by Shannon's theorem. We study lower bounds on the size of s…