
M. H. de Carvalho

C. H. C. Little
Keywords:
Graph theory, Pfaffian graphs, even directed circuits
Abstract
A thicket in a graph $G$ is defined as a set of even circuits such that every edge lies in an even number of them. If $G$ is directed, then each circuit in the thicket has a well defined directed parity. The parity of the thicket is the sum of the parities of its members, and is independent of the orientation of $G$. We study the problem of determining the parity of a thicket $\mathcal{T}$ in terms of structural properties of $\mathcal{T}$. Specifically, we reduce the problem to studying the case where the underlying graph $G$ is cubic. In this case we solve the problem if $\mathcal{T} = 3$ or $G$ is bipartite. Some applications to the problem of characterising Pfaffian graphs are also considered.