Article ID Journal Published Year Pages File Type
4654975 European Journal of Combinatorics 2006 14 Pages PDF
Abstract

A trigraph is a multigraph with half-edges colored in three colors. We introduce the notion of an Eulerian coloring of a trigraph and show that the existence of two orthogonal Eulerian colorings in a special class of trigraphs is closely related to the bipartizing matchings conjecture of Fleischner, and hence to the cycle double cover conjecture and Tutte’s 5-flow conjecture. We prove that every trigraph has an Eulerian coloring and that a rainbow cubic trigraph has a pair of orthogonal Eulerian colorings if and only if it has a perfect matching.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, , ,