KIT | KIT-Bibliothek | Impressum | Datenschutz

Regular colorings in regular graphs

Bernshteyn, Anton; Khormali, Omid; Martin, Ryan R.; Rollin, Jonathan; Rorabaugh, Danny; Shan, Songlin; Uzzell, Andrew

Abstract:
An (r−1,1)-coloringof anr-regular graphGis an edge coloring (witharbitrarily many colors) such that each vertex is incident tor−1 edgesof one color and 1 edge of a different color. In this paper, we completelycharacterize all 4-regular pseudographs (graphs that may contain paralleledges and loops) which do not have a (3,1)-coloring. Also, for eachr≥6 we construct graphs that are not (r−1,1)-colorable and, more generally, arenot (r−t, t)-colorable for smallt.

Open Access Logo


Zugehörige Institution(en) am KIT Fakultät für Mathematik (MATH)
Publikationstyp Zeitschriftenaufsatz
Publikationsjahr 2020
Sprache Englisch
Identifikator ISSN: 1234-3099, 2083-5892
KITopen-ID: 1000127020
Erschienen in Discussiones mathematicae / Graph theory
Band 40
Heft 3
Seiten 795-806
Externe Relationen Abstract/Volltext
Schlagwörter edge coloring, graph factors, regular graphs
Nachgewiesen in Scopus
Web of Science
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page