Maximal edge-colorings of graphs

Abstract

For graph G of order n a maximal edge-coloring is a proper partial coloring with fixed number of colors (equal to n or n-1) such that adding any edge to G in any color makes it improper. Meszka and Tyniec proved that for some numbers of edges it is impossible to find such a graph, and provided constructions for some other numbers of edges. However, for many values, the problem remained open. We give a complete solution of this problem for all even values of n and for odd n not smaller than 37.