Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4654975 | European Journal of Combinatorics | 2006 | 14 Pages |
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
Zdeněk Dvořák, Tomáš Kaiser, Daniel Král’,