Regular colorings in regular graphs
Anton Bernshteyn, Omid Khormali, Ryan R. Martin, Jonathan Rollin, Danny Rorabaugh, Songling Shan, Andrew J. Uzzell · Discussiones Mathematicae Graph Theory · 2018
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 (rt, t)-colorable for small t.