Publication details
Eulerian colorings and the bipartizing matchings conjecture of Fleischner
| Authors | |
|---|---|
| Year of publication | 2006 |
| Type | Article in Periodical |
| Magazine / Source | European Journal of Combinatorics |
| Citation | |
| Doi | http://dx.doi.org/10.1016/j.ejc.2006.06.002 |
| Description | 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. (c) 2006 Elsevier Ltd. All rights reserved. |