The classification of complete graphs \(K_n\) on \(f\)-coloring (Q2574329)

Given a graph \(G = (V,E)\) and a function \(f:V \to \mathbb{Z}^+\), an \(f\)-coloring of \(G\) is an edge coloring such that each color appears at each vertex \(v \in V\) at most \(f(v)\) times. The \(f\)-chromatic index \(\chi'_f(G)\) is the minimum number of colors required for an \(f\)-coloring of \(G\). \textit{S. L. Hakimi} and \textit{O. Kariv} [J. Graph Theory 10, 139--154 (1986; Zbl 0601.05021)] proved that for any graph \(G\), \(\Delta_f \leq \chi'_f(G) \leq \Delta_f + 1\) where \(\Delta_f = \max_{v \in V} \{\lceil \frac{\deg(v)}{f(v)}\rceil\}\); thus, in analogy with the Vizing theorem, \(G\) is of class \(C_f \;1\) if \(\chi'_f(G) = \Delta_f\), and of class \(C_f\;2\) otherwise. In the paper under review, the authors present the classification of complete graphs on \(f\)-coloring, proving that a complete graph \(K_n\) is of class \(C_f\;2\) if and only if \(n\) is odd and there exists an odd integer \(k\) such that, for every vertex \(v\), \(f(v) = k\) and \(k | \deg(v)\).