CHROMATIC AND FLOW POLYNOMIALS FOR DIRECTED-GRAPHS

We consider two related combinatorial problems for directed graphs. The first is one in which each of the nu vertices is coloured in one of the colours in C = {0, 1,.., lambda - 1} with the constraint that (c(j) - c(i)) mod-lambda, when chosen as an element of C, must be non-zero and even for all arcs (i, j), where c(i) is the colour of vertex i. Also considered are the closely related problems when the even constraint is replaced by odd, and, for both the even and odd cases, when the non-zero constraint is relaxed to give improper colourings. The colouring problems with the even (odd) constraint will be known as ''even-PD'' (''odd-PD'') problems since the integer c(i) associated with vertex i may be thought of as a potential and (c(j)-c(i)) mod-lambda. as a potential difference (PD). In the standard graph colouring problem the number of improper colourings is trivially given by lambda(nu) and the number of proper colourings may also be interpolated by a polynomial in lambda of degree nu known as the chromatic polynomial of the graph. For the even (odd)-PD problem, the properties of the numbers of (improper or proper) colourings are distinguished by the parity of lambda. For even lambda, the numbers of colourings are the same for all directings of a given undirected graph and the problem is easily related to the standard colouring problem; it follows that the number of colourings for lambda = 2, 4, 6,... may again be interpolated by a polynomial in lambda of degree nu. One of the main results of the paper is to show that the number of colourings for lambda = 3, 5, 7,... may also be so interpolated but with a polynomial which is different from that for even lambda and which has degree at most nu. A different polynomial may be required for different directings of the same undirected graph and for each odd-PD problem there is an equivalent even-PD problem on the reversed graph. We also consider even or odd mod-lambda PDs when the potential difference on a particular are has the value beta. For even lambda these are related to similar standard mod-lambda PDs and, for fixed beta, their numbers are interpolated by a polynomial in lambda which for positive beta depends only on the parity of beta. For odd lambda, the values for even beta, and odd beta separately, also have polynomial dependence on beta and are directing dependent. The even-beta polynomial when lambda = 1 and beta = 0 has the value 1 or 0 depending on whether or not there is a directed cut containing the chosen edge. For planar graphs, each of the above problems is equivalent to counting mod-lambda flows on the dual graph. The second problem we consider is the extension of the above results to even (odd)-flow problems on non-planar graphs. These combinatorial problems have their origins in statistical mechanics. (C) 1994 Academic Press, Inc.