DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2019: 0.755

SCImago Journal Rank (SJR) 2019: 0.600

Rejection Rate (2018-2019): c. 84%

Discussiones Mathematicae Graph Theory

Article in press


Authors:

A. Bernshteyn, O. Khormali, R.R. Martin, J. Rollin, D. Rorabaugh, S. Shan, A. Uzzell

Title:

Regular colorings in regular graphs

Source:

Discussiones Mathematicae Graph Theory

Received: 2017-10-04, Revised: 2018-05-07, Accepted: 2018-05-10, https://doi.org/10.7151/dmgt.2149

Abstract:

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\geq 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

PDF
Close