Pfaffian orientations of graphs
by Robin Thomas
Georgia Institute of Technology
ABSTRACT
An orientation of a graph G is Pfaffian if every even cycle C
such that G\V(C) has a perfect matching has an odd number of edges
directed in either direction of the cycle. The significance of
Pfaffian orientations is that if a graph has one, then the number
of perfect matchings can be computed in polynomial time.
The speaker will present a structural characterization of bipartite
graphs that have a Pfaffian orientation, obtained independently by
W. McCuaig, and by N. Robertson, P.D. Seymour and the presenter.
The characterization gives rise to a quadratic recognition algorithm, and
has other applications. For instance, it gives an answer to a question
of Polya about permanents, it solves the even directed cycle problem,
it solves the sign-nonsingular matrix problem for square matrices,
it gives a characterization of "minimally nonbipartite" hypergraphs,
and it can be used to derive other results about packing in digraphs.
An attempt at extending the characterization to general graphs is
related to a matching decomposition procedure of Kotzig, Lovasz and
Plummer, and leads to a generation result for "bricks", the building
blocks of the decomposition.
Back to the
Discrete Mathematics and its Applications home page.