(p,q)-odd digraphs

A digraph D is (p,q)-odd if and only if any subdivision of D contains a directed cycle of length different from p mod q. A characterization of (p,q)-odd digraphs analogous to the Seymour-Thomassen characterization of (1, 2)-odd digraphs is provided. In order to obtain this characterization we study the lattice generated by the directed cycles of a strongly connected digraph. We show that the sets of directed cycles obtained from an ear decomposition of the digraph in a natural way are bases of this lattice. A similar result does not hold for undirected graphs. However we construct, for each undirected 2-connected graph G, a set of cycles of G which form a basis of the lattice generated by the cycles of G. © 1996 John Wiley & Sons, Inc.