Volume 21, No 5, 2014, P. 316
UDC 519.174
A. Yu. Bernshtein
3Regular subgraphs and (3, 1)colorings of 4regular pseudographs
Abstract:
Let G be a 4regular 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 3regular subgraphs in G. We prove that every connected 4regular pseudograph which contains a 3regular subgraph has a (3, 1)coloring. Moreover, every 4regular 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 3regular 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 3regular subgraph.
Ill. 8, bibliogr. 20.
Keywords: 4regular graph, edge coloring.
Bernshtein Anton Yurievich ^{1}
1. Novosibirsk State University,
2 Pirogov St., 630090 Novosibirsk, Russia
email: bahtoh@gmail.com
