Volume 21, No 5, 2014, P. 3-16

UDC 519.174
A. Yu. Bernshtein  
3-Regular subgraphs and (3, 1)-colorings of 4-regular pseudographs

Abstract:
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.

Keywords: 4-regular graph, edge coloring.

Bernshtein Anton Yurievich ¹
1. Novosibirsk State University,
2 Pirogov St., 630090 Novosibirsk, Russia
e-mail: bahtoh@gmail.com