A biased graph Omega consists of a graph Gamma and a class of circles in Gamma (edge sets of simple, closed paths), called balanced, such that no theta subgraph contains exactly two balanced circles. An edge set is balanced if (simplifying slightly) every circle in it is balanced. Biased graphs generalize ordinary graphs, which behave like biased graphs in which every circle is balanced. We define and study the chromatic, dichromatic, and Whitney number polynomials of a biased graph, which generalize those of an ordinary graph. We employ an algebraic definition since not all biased graphs can be colored. We show that the polynomials enjoy many properties that are familiar in ordinary graph theory, such as convolutional and partition expansions, close connections with the bias and lift matroids of Omega, and deletion-contraction invariance of the dichromatic polynomial. They also have the novel feature of being reducible to more readily computable related polynomials that have no analogs in ordinary graph theory. We apply our results to evaluate Whitney numbers and other invariants of the bias and lift matroids, to characterize the biased graphs which have an unbalanced edge at every node and whose bias matroid is a series-parallel network, and to calculate the invariants of some types of biased graphs, such as those where no circle is balanced and some which are similar to Dowling lattices and classical root systems. For the latter we also characterize supersolvability, a matroid property which implies the characteristic polynomial has positive integral roots. (C) 1995 Academic Press, Inc. [References: 41]
展开▼
