Let be a simple graph of maximum degree . The edges of can be colored with at most colors by Vizing's theorem. We study lower bounds on the size of subgraphs of that can be colored with colors. Vizing's theorem gives a bound of . This is known to be tight for cliques when is even. However, for it was improved to by Albertson and Haas [Discrete Math., 148 (1996), pp. 1--7] and later to by Rizzi [Discrete Math., 309 (2009), pp. 4166--4170]. It is tight for , the graph isomorphic to a with one edge subdivided. We improve previously known bounds for , under the assumption that for , graph is not isomorphic to , , and , respectively. For these are the first results which improve over the Vizing's bound. We also show a new bound for subcubic multigraphs not isomorphic to with one edge doubled. In the second part, we give approximation algorithms for the maximum -edge-colorable subgraph problem, where given a graph (without any bound on its maximum degree or other restrictions) one has to find a -edge-colorable subgraph with the maximum number of edges. In particular, when is simple for we obtain approximation ratios of , , , and , respectively. We also present a -approximation for when is a multigraph. The approximation algorithms follow from a new general framework that can be used for any value of .