  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 $26/31|E|$ by Albertson and Haas [Parsimonious
edge colorings, Disc. Math. 148, 1996] and later to $6/7|E|$ by Rizzi
[Approximating the maximum 3-edge-colorable subgraph problem, Disc. Math. 309,
2009]. 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,...,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 maximum number of edges. In particular, when G is simple for
k=3,4,5,6,7 we obtain approximation ratios of 13/15, 9/11, 19/22, 23/27 and
22/25, respectively. We also present a 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.
