Beyond the Vizing's Bound for at Most Seven Colors
Marcin Kamiński, Łukasz Kowalik · SIAM Journal on Discrete Mathematics · 2014
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 of $G$ that can be colored with $\Delta$ colors. Vizing's theorem gives a bound of $\frac{\Delta}{\Delta+1}|E|$. This is known to be tight for cliques $K_{\Delta+1}$ when $\Delta$ is even. However, for $\Delta=3$ it was improved to $\frac{26}{31}|E|$ by Albertson and Haas [Discrete Math., 148 (1996), pp. 1--7] and later to $\frac{6}7|E|$ by Rizzi [Discrete Math., 309 (2009), pp. 4166--4170]. It is tight for $B_3$, the graph isomorphic to a $K_4$ with one edge subdivided. We improve previously known bounds for $\Delta\in\{3,\ldots,7\}$, under the assumption that for $\Delta=3,4,6$, graph $G$ is not isomorphic to $B_3$, $K_5$, and $K_7$, respectively. For $\Delta \geq 4$ these are the first results which improve over the Vizing's bound. We also show a new bound for subcubic multigraphs not isomorphic to $K_3$ with one edge doubled. In the second part, we give approximation algorithms for the maximum $k$-edge-colorable subgraph problem, where given a graph $G$ (without any bound on its maximum degree or other restrictions) one has to find a $k$-edge-colorable subgraph with the maximum number of edges. In particular, when $G$ is simple for $k=3,4,5,6,7$ we obtain approximation ratios of $\frac{13}{15},\frac{9}{11}$, $\frac{19}{22}$, $\frac{23}{27}$, and $\frac{22}{25}$, respectively. We also present a $\frac{7}{9}$-approximation for $k=3$ when $G$ is a multigraph. The approximation algorithms follow from a new general framework that can be used for any value of $k$.