1. Regular Colorings in Regular Graphs
- Author
-
Bernshteyn Anton, Khormali Omid, Martin Ryan R., Rollin Jonathan, Rorabaugh Danny, Shan Songling, and Uzzell Andrew J.
- Subjects
edge coloring ,graph factors ,regular graphs ,05c15 ,Mathematics ,QA1-939 - Abstract
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.
- Published
- 2020
- Full Text
- View/download PDF