Maximal edge-colorings of graphs

Main Article Content

Sebastian Babiński Andrzej Grzesik


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.

Article Details

How to Cite
Babiński, S., & Grzesik, A. (2019). Maximal edge-colorings of graphs. Acta Mathematica Universitatis Comenianae, 88(3), 403-407. Retrieved from