Beyond the Vizing's bound for at most seven colors

Marcin Kamiński, Łukasz Kowalik

Let $G=(V,E)$ be a simple graph of maximum degree $\Delta$. The edges of $G$ can be colored with at most $\Delta +1$ colors by Vizing's theorem. We study lower bounds on the size of subgraphs…