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/