A. Bernshteyn, O. Khormali, R.R. Martin, J. Rollin, D. Rorabaugh, S. Shan, A. Uzzell
Regular colorings in regular graphs
Discussiones Mathematicae Graph Theory
Received 04.10.2017, Revised 07.05.2018, Accepted 10.05.2018, doi: 10.7151/dmgt.2149
An (r-1,1)-coloring of an r-regular graph G is an edge coloring (with arbitrarily many colors) such that each vertex is incident to r-1 edges of one color and 1 edge of a different color. In this paper, we completely characterize all 4-regular pseudographs (graphs that may contain parallel edges and loops) which do not have a (3,1)-coloring. Also, for each r≥ 6 we construct graphs that are not (r-1,1)-colorable and, more generally, are not (r-t,t)-colorable for small t.
edge coloring, graph factors, regular graphs