The Classification of Regular Graphs on \(f\)-colorings

Abstract

An \(f\)-coloring of a graph \(G\) is a coloring of edges of \(E(G)\) such that each color appears at each vertex \(v \in V(G)\) at most \(f(v)\) times. The minimum number of colors needed to \(f\)-color \(G\) is called the \(f\)-chromatic index of \(G\) and denoted by \(\chi’_f(G)\). Any simple graph \(G\) has the \(f\)-chromatic index equal to \(\Delta_f(G)\) or \(\Delta_f(G) + 1\), where \(\Delta_f(G) = \max_{v \in V}\{\lceil \frac{d(v)} {f(v)}\rceil\}\). If \(\chi’_f(G) = \Delta_f(G)\), then \(G\) is of \(C_f\) \(1\); otherwise \(G\) is of \(C_f\) \(2\). In this paper, two sufficient conditions for a regular graph to be of \(C_f\) \(1\) or \(C_f\) \(2\) are obtained and two necessary and sufficient conditions for a regular graph to be of \(C_f\) \(1\) are also presented.