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/

[1] Distel R., Teoriya grafov, Izd-vo In-ta matematiki, Novosibirsk, 2002, 336 pp.

[2] Lidl R., Niderraiter G., Konechnye polya, v. 1, Mir, M., 1988, 430 pp. | MR | Zbl

[3] Tashkinov V. A., “3-odnorodnye chasti 4-odnorodnykh grafov”, Mat. zametki, 36:2 (1984), 239–259 | MR | Zbl

[4] Addario-Berry L., Dalal K., Reed B. A., “Degree constrained subgraphs”, Discrete Appl. Math., 156:7 (2008), 1168–1174 | DOI | MR | Zbl

[5] Alon N., Friedland S., Kalai G., “Regular subgraphs of almost regular graphs”, J. Comb. Theory Ser. B, 37:1 (1984), 79–91 | DOI | MR | Zbl

[6] Alon N., Friedland S., Kalai G., “Every 4-regular graph plus an edge contains a 3-regular subgraph”, J. Comb. Theory Ser. B, 37:1 (1984), 92–93 | DOI | MR | Zbl

[7] Alon N., “Combinatorial Nullstellensatz”, J. Comb. Probab. Comput., 8:1–2 (1999), 7–29 | DOI | MR | Zbl

[8] Berge C., Las Vergnas M., “On the existence of subgraphs with degree constraints”, Indagationes Mathematicae (Proc.), 81:1 (1978), 165–176 | DOI | MR | Zbl

[9] Bondy J. A., Murty U. S. R., Graph theory, Grad. Texts Math., 244, Springer-Verl., Berlin, 2008, 655 pp. | DOI | MR | Zbl

[10] Chvátal V., Fleischner H., Sheehan J., Thomassen C., “Three-regular subgraphs of four-regular graphs”, J. Graph Theory, 3:4 (1979), 371–386 | DOI | MR | Zbl

[11] Cornuéjols G., “General factors of graphs”, J. Comb. Theory Ser. B, 45:2 (1988), 185–198 | DOI | MR | Zbl

[12] Heinrich K., Hell P., Kirkpatrick D. G., Liu G., “A simple existence criterion for $(g)$-factors”, Discrete Math., 85:3 (1990), 313–317 | DOI | MR | Zbl

[13] Kano M., Saito A., “$[a,b]$-Factors of graphs”, Discrete Math., 47 (1983), 113–116 | DOI | MR | Zbl

[14] Kano M., “Factors of regular graphs”, J. Comb. Theory Ser. B, 41:1 (1986), 27–36 | DOI | MR | Zbl

[15] Lovász L., “Subgraphs with prescribed valencies”, J. Comb. Theory, 8:4 (1970), 391–416 | DOI | MR | Zbl

[16] Moreno O., Zinoviev V. A., “Some sufficient conditions for 4-regular graphs to have 3-regular subgraphs”, Lect. Notes Comput. Sci., 781, 1994, 164–171 | DOI | MR | Zbl

[17] Moreno O., Zinoviev V. A., “Three-regular subgraphs of four-regular graphs”, Eur. J. Comb., 19:3 (1998), 369–373 | DOI | MR | Zbl

[18] Olson J. E., “A combinatorial problem on finite Abelian groups. II”, J. Number Theory, 1:2 (1969), 195–199 | DOI | MR | Zbl

[19] Sebö A., “General antifactors of graphs”, J. Comb. Theory Ser. B, 58:2 (1993), 174–184 | DOI | MR | Zbl

[20] Tutte W. T., “The subgraph problem”, Ann. Discrete Math., 3 (1978), 289–295 | DOI | MR | Zbl