Geodesic
Regular Colorings in Regular Graphs
Discussiones Mathematicae. Graph Theory, Tome 40 (2020) no. 3, pp. 795-806.

Voir la notice de l'article provenant de la source Library of Science

An (r − 1, 1)-coloring of an r-regular graph G is an edge coloring (with arbitrarily many colors) such that each vertex is incident to r − 1 edges of one color and 1 edge of a different color. In this paper, we completely characterize all 4-regular pseudographs (graphs that may contain parallel edges and loops) which do not have a (3, 1)-coloring. Also, for each r ≥ 6 we construct graphs that are not (r −1, 1)-colorable and, more generally, are not (r − t, t)-colorable for small t.
Keywords: edge coloring, graph factors, regular graphs 
@article{DMGT_2020_40_3_a6,
     author = {Bernshteyn, Anton and Khormali, Omid and Martin, Ryan R. and Rollin, Jonathan and Rorabaugh, Danny and Shan, Songling and Uzzell, Andrew J.},
     title = {Regular {Colorings} in {Regular} {Graphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {795--806},
     publisher = {mathdoc},
     volume = {40},
     number = {3},
     year = {2020},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2020_40_3_a6/}
}
TY  - JOUR
AU  - Bernshteyn, Anton
AU  - Khormali, Omid
AU  - Martin, Ryan R.
AU  - Rollin, Jonathan
AU  - Rorabaugh, Danny
AU  - Shan, Songling
AU  - Uzzell, Andrew J.
TI  - Regular Colorings in Regular Graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2020
SP  - 795
EP  - 806
VL  - 40
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2020_40_3_a6/
LA  - en
ID  - DMGT_2020_40_3_a6
ER  - 
%0 Journal Article
%A Bernshteyn, Anton
%A Khormali, Omid
%A Martin, Ryan R.
%A Rollin, Jonathan
%A Rorabaugh, Danny
%A Shan, Songling
%A Uzzell, Andrew J.
%T Regular Colorings in Regular Graphs
%J Discussiones Mathematicae. Graph Theory
%D 2020
%P 795-806
%V 40
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2020_40_3_a6/
%G en
%F DMGT_2020_40_3_a6
Bernshteyn, Anton; Khormali, Omid; Martin, Ryan R.; Rollin, Jonathan; Rorabaugh, Danny; Shan, Songling; Uzzell, Andrew J. Regular Colorings in Regular Graphs. Discussiones Mathematicae. Graph Theory, Tome 40 (2020) no. 3, pp. 795-806. http://geodesic.mathdoc.fr/item/DMGT_2020_40_3_a6/

[1] S. Akbari and M. Kano, {k, r − k}-factors of r-regular graphs, Graphs Combin. 30 (2014) 821–826. doi:10.1007/s00373-013-1324-x

[2] J. Akiyama and M. Kano, Factors and Factorizations of Graphs: Proof Techniques in Factor Theory (Springer, Heidelberg, 2011). doi:10.1007/978-3-642-21919-1

[3] M. Axenovich and J. Rollin, Brooks type results for conflict-free colorings and {a, b}-factors in graphs, Discrete Math. 338 (2015) 2295–2301. doi:10.1016/j.disc.2015.05.020

[4] A.Y. Bernshteyn, 3 - regular subgraphs and (3, 1) - colorings of 4 - regular pseudographs, J. Appl. Ind. Math. 8 (2014) 458–466. doi:10.1134/S1990478914040024

[5] B. Bollobás, A. Saito and N.C. Wormald, Regular factors of regular graphs, J. Graph Theory 9 (1985) 97–103. doi:10.1002/jgt.3190090107

[6] J.A. Bondy and U.S.R. Murty, Graph Theory with Applications (American Elsevier Publishing Co., New York, 1976).

[7] F.R.K. Chung and R.L. Graham, Recent results in graph decompositions, in: Combinatorics Proc. 8th British Combinatorial Conference (Swansea, 1981), London Math. Soc. Lecture Note Ser. 52 (1981) 103–123.

[8] L. Lovász, The factorization of graphs. II, Acta Math. Hungar. 23 (1972) 223–246. doi:10.1007/BF01889919

[9] H. Lu, D.G.L. Wang and Q. Yu, On the existence of general factors in regular graphs, SIAM J. Discrete Math. 27 (2013) 1862–1869. doi:10.1137/120895792

[10] J. Petersen, Die Theorie der regulären graphs, Acta Math. 15 (1891) 191–220. doi:10.1007/BF02392606

[11] M.D. Plummer, Graph factors and factorization: 1985 – 2003: A survey, Discrete Math. 307 (2007) 791–821. doi:10.1016/j.disc.2005.11.059

[12] V.A. Tashkinov, 3-regular parts of 4-regular graphs, Mat. Zametki 36 (1984) 239–259.

[13] V.A. Tashkinov, Regular parts of regular pseudographs, Mat. Zametki 43 (1988) 263–275.

[14] W.T. Tutte, The subgraph problem, Ann. Discrete Math. 3 (1978) 289–295. doi:10.1016/S0167-5060(08)70514-4