$3$-regular subgraphs and $(3,1)$-colorings of $4$-regular pseudographs

Let $G$ be a $4$-regular pseudograph. A $(3,1)$-coloring of $G$ is an edge coloring of $G$, such that every vertex of $G$ is incident exactly with three edges of one color and with one edge of another color. The properties of $(3,1)$-colorings are closely related to the existence of $3$-regular subgraphs in $G$. We prove that every connected $4$-regular pseudograph which contains a $3$-regular subgraph has a $(3,1)$-coloring. Moreover, every $4$-regular pseudograph without parallel edges (but, maybe, with loops) admits a $(3,1)$-coloring. This result serves as an indirect confirmation of the assumption (unproved) that every such graph contains a $3$-regular subgraph. We also analyze the problem of determining the minimal number of colors needed for a $(3,1)$-coloring of a given graph. Finally, we prove that the existence of a $(3,1)$-coloring which satisfies some additional properties (an ordered $(3,1)$-coloring) is equivalent to the existence of a $3$-regular subgraph. Ill. 8, bibliogr. 20.