On restricted colorings of $(d,s)$-edge colorable graphs
Lan Anh Pham · arXiv (Cornell University) · 2019
A cycle is $2$-colored if its edges are properly colored by two distinct colors. A $(d,s)$-edge colorable graph $G$ is a $d$-regular graph that admits a proper $d$-edge coloring in which every edge of $G$ is in at least $s-1$ $2$-colored $4$-cycles. Given a $(d,s)$-edge colorable graph $G$ and a list assigment $L$ of forbidden colors for the edges of $G$ satisfying certain sparsity conditions, we prove that there is a proper $d$-edge coloring of $G$ that avoids $L$, that is, a proper edge coloring $φ$ of $G$ such that $φ(e) otin L(e)$ for every edge $e$ of $G$.