Using edge cuts and Tutte’s 1-Factor Theorem, Tashkinov (1982) settled the Berge–Sauer conjecture: Every 4-regular simple graph does indeed contain a 3-regular subgraph. The question remains open, however, for 4-regular pseudographs—that is,

for graphs with loops and multi-edges allowed. Bernshteyn (2014) introduced the use of edge-colorings as an approach to this problem, proving that a 4-regular pseudograph contains a 3-regular subgraph if and only if it admits an ordered (3, 1)-coloring. A (3, 1)-coloring of a 4-regular graph is an edge coloring in which every vertex v is incident to 3 edges of a color iv and 1 edge of a different color jv. The coloring is ordered provided the colors are linearly ordered and iv < jv at every vertex v. We completely characterize (3, 1)-colorable pseudograph, though a characterization of the ordered-(3, 1)-colorable pseudograph remains at large.

This is joint work with Bernshteyn, Khormali, Martin, Rollin, Shan, and Uzzell.