Characterization of graphs without even $F$-orientations

Abstract

A graph $G$ is $1$-extendible if every edge belongs to at least one $1$-factor of $G$. Let $G$ be a graph with a $1$-factor $F$. Then an even $F$-orientation of $G$ is an orientation in which each $F$-alternating cycle has exactly an even number of edges directed in the same fixed direction around the cycle. In this paper, we examine the structure of 1-extendible graphs $G$ which have no even $F$-orientation where $F$ is a fixed $1$-factor of $G$. In the case of graphs of connectivity at least four and k-regular graphs for $k\ge 3$ we give a complete characterization.

31 pages, 9 figures