Veröffentlichung

Titel:

Regular colorings and factors of regular graphs

AutorInnen:

Anton Bernshteyn
Omid Khormali
Ryan R. Martin
Jonathan Rollin
Danny Rorabaugh
Songling Shan
Andrew J. Uzzell

Kategorie:

Artikel in Zeitschriften

erschienen in:

Discussiones Mathematicae Graph Theory, Vol. 40, No. 3, pp. 795-806, 2020

Abstract:

An (r−1,1)-coloring of an r-regular graph G is an edge coloring 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. An {r−1,1}-factor of an r-regular graph is a spanning subgraph in which each vertex has degree either r−1 or 1. We prove various conditions that that must hold for any vertex-minimal 5-regular pseudographs without (4,1)-colorings or without {4,1}-factors. Finally, 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.

Download:

Discussiones Mathematicae Graph Theory

BibTeX-Eintrag:

@article{BKMRRS20, author = {Anton Bernshteyn and Omid Khormali and Ryan R. Martin and Jonathan Rollin and Danny Rorabaugh and Songlin Shan and Andrew J. Uzzell}, title = {Regular colorings in regular graphs}, journal = {Discuss. Math. Graph Theory}, volume = {40}, number = {3}, pages = {795--806}, year = {2020}, doi = {10.7151/dmgt.2149}, }