Before revision:  For graphs with maximum degree \Delta , one can do better.
After revision:  For bounded-multiplicity problem instances , one can do better.