Regular colorings and factors of regular graphs
Bernshteyn, Anton, Khormali, Omid, Martin, Ryan R., Rollin, Jonathan, Danny Rorabaugh, Songling Shan, Andrew J. Uzzell · arXiv (Cornell University) · 2016
A graph G has an S-factor if there exists a spanning subgraph F of G such that for all v in V: deg_F(v) in S. The simplest example of such factor is a 1-factor, which corresponds to a perfect matching in a graph. In this paper we study the computational complexity of finding S-factors in regular graphs. Our techniques combine some classical as well as recent tools from graph theory.