2019/12/19 by Babiński, Sebastian, Grzesik, Andrzej
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1912.09538
For a graph G of order n a maximal edge coloring is a proper edge coloring with χ'(Kn) colors such that adding any edge to G in any color makes it improper. Meszka and Tyniec proved that for some values of the number of edges there are no graphs with a maximal edge coloring, while for some other values, they provided constructions of such graphs. However, for many values of the number of edges determining whether there exists any graph with a maximal edge coloring remained open. We give a complete solution of this problem.