We show that a graph has an orientation under which every circuit of even length is clockwise odd if and only if the graph contains no subgraph which is, after the contraction of at most one circuit of odd length, an even subdivision of K2,3. In fact we give a more general characterisation of graphs that have an orientation under which every even circuit has a prescribed clockwise parity. Moreover we show that this characterisation has an equivalent analogue for signed graphs. | Even circuits of prescribed clockwise parity Ilse Fischer Universitat Klagenfurt A-9020 Klagenfurt Austria . Little Massey University Palmerston North New Zealand Submitted Jul 11 2003 Accepted Oct 8 2003 Published Nov 24 2003 MR Subject Classifications 05C38 05C20 Abstract We show that a graph has an orientation under which every circuit of even length is clockwise odd if and only if the graph contains no subgraph which is after the contraction of at most one circuit of odd length an even subdivision of K2 3. In fact we give a more general characterisation of graphs that have an orientation under which every even circuit has a prescribed clockwise parity. Moreover we show that this characterisation has an equivalent analogue for signed graphs. We were motivated to study the original problem by our work on Pfaffian graphs which are the graphs that have an orientation under which every alternating circuit is clockwise odd. Their significance is that they are precisely the graphs to which Kasteleyn s powerful method for enumerating perfect matchings may be applied. THE ELECTRONIC JOURNAL OF COMBINATORICS 10 2003 R45 1 1 Introduction Consider the three even circuits in K2 3. Is it possible to find an orientation under which all these circuits are clockwise odd if the clockwise parity of a circuit of even length is defined as the parity of the number of edges that are directed in agreement with a specified sense However K2 3 is oriented one observes that the total number of clockwise even circuits is odd and therefore it is not possible to find such an orientation. In this paper we present a characterisation in terms of forbidden subgraphs of the graphs that have an orientation under which every even circuit is clockwise odd. It will turn out that the non-existence of such an orientation can in a sense always be put down to an even subdivision of K2 3. See Corollary 1. We were motivated to study this problem by our
