Eulerian Circuits with No Monochromatic Transitions in Edge-Colored Digraphs with all Vertices of Outdegree Three
James M. Carraher, Stephen G. Hartke · SIAM Journal on Discrete Mathematics · 2017
A colored eulerian digraph is an eulerian digraph $G$ where a color is assigned to the tail of each edge and a color is assigned to the head of each edge. A compatible circuit is an eulerian circuit such that for every two consecutive edges $uv$ and $vw$ of the circuit, the color of the head of $uv$ is different from the color of the tail of $vw$. Let $S_3$ be the set of vertices of outdegree and indegree three that have exactly three colors on the incident edges where each color appears on exactly one incoming and exactly one outgoing edge. In this paper we consider graphs where all the vertices are in $S_3$. We show that in several special cases we can determine if a graph has a compatible circuit. Our characterization in these cases give rise to a polynomial-time algorithm that determines the existence of a compatible circuit and provides a compatible circuit if one exists.