Geodesic
$3$-regular subgraphs and $(3,1)$-colorings of $4$-regular pseudographs
Diskretnyj analiz i issledovanie operacij, Tome 21 (2014) no. 5, pp. 3-16

Voir la notice de l'article provenant de la source Math-Net.Ru

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. 
@article{DA_2014_21_5_a0,
     author = {A. Yu. Bernshtein},
     title = {$3$-regular subgraphs and $(3,1)$-colorings of $4$-regular pseudographs},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {3--16},
     publisher = {mathdoc},
     volume = {21},
     number = {5},
     year = {2014},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2014_21_5_a0/}
}
TY  - JOUR
AU  - A. Yu. Bernshtein
TI  - $3$-regular subgraphs and $(3,1)$-colorings of $4$-regular pseudographs
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2014
SP  - 3
EP  - 16
VL  - 21
IS  - 5
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2014_21_5_a0/
LA  - ru
ID  - DA_2014_21_5_a0
ER  - 
%0 Journal Article
%A A. Yu. Bernshtein
%T $3$-regular subgraphs and $(3,1)$-colorings of $4$-regular pseudographs
%J Diskretnyj analiz i issledovanie operacij
%D 2014
%P 3-16
%V 21
%N 5
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2014_21_5_a0/
%G ru
%F DA_2014_21_5_a0
A. Yu. Bernshtein. $3$-regular subgraphs and $(3,1)$-colorings of $4$-regular pseudographs. Diskretnyj analiz i issledovanie operacij, Tome 21 (2014) no. 5, pp. 3-16. http://geodesic.mathdoc.fr/item/DA_2014_21_5_a0/