Graph polynomials: some questions on the edge

The preeminent graph polynomial is arguably the Tutte polynomial, due to W.T. Tutte [106, 107] and closely related to the Whitney rank generating function [116].

The Whitney rank generating function $R(G;x,y)$ of a graph $G$ is the bivariate polynomial defined by

The Tutte polynomial $T(G;x,y)$ may be defined by

for any edge $e\in E(G)$. The polynomials of Whitney and Tutte are related by a simple coordinate translation: $T(G;x,y)=R(G;x-1,y-1)$ [106, 107].

The recurrence (1) is the most fundamental property of the Tutte polynomial, and one of Tutte’s major conceptual contributions in [106] was to base the theory on this relation, a fundamental conceptual advance upon the pioneering work of Whitney [116]. For a history of these polynomials, see [40].

A graph $G$ is Tutte equivalent to a graph $H$ if $T(G;x,y)=T(H;x,y)$ [109, 116, 117]. Graphs with isomorphic cycle matroids are Tutte equivalent, since the Tutte polynomial of a graph depends only on its cycle matroid. But, as an equivalence relation on graphs, Tutte equivalence is coarser than cycle matroid isomorphism. Tutte [109] gave two graphs, due to M.C. Gray, which are not isomorphic, and do not even have isomorphic cycle matroids, but which have the same Tutte polynomial: see Figure 1. Many other such pairs are known.

The most famous specialisation of the Tutte polynomial is the chromatic polynomial $P(G;q)=(-1)^{\rho(G)}q^{k(G)}T(G;-q+1,0)$ introduced by Birkhoff in [8]. For $q\in\mathbb{N}$, it gives the number of $q$-colourings of $G$. Two graphs are chromatically equivalent if they have the same chromatic polynomial.

Tutte-Whitney polynomials have been generalised from graphs to many other combinatorial objects [26, 33]. For structures on which deletion and contraction operations exist, Krajewski, Moffatt and Tanasa [66] show how to use Hopf algebras to define a polynomial that may reasonably be called the Tutte polynomial for those structures and which satisfies a deletion-contraction relation.

We introduce the partition functions of three interaction models on graphs: the Ising, Potts and Ashkin-Teller models. Our main focus later will be on the Ashkin-Teller model.

The set of edges of a graph $G$ whose endpoints receive the same colour under a $q$-assignment $f$ is denoted by $E^{+}(f)$; these edges are sometimes called bad since they are not properly coloured in the sense of graph colouring. The set of edges whose endpoints are differently coloured under $f$ is denoted by $E^{-}(f)$; these edges are sometimes called good. Note that $E^{+}(f)\cup E^{-}(f)=E$. So the positive and negative signs in superscripts here represent “bad” and “good”, respectively, which is the opposite of their connotations in ordinary English usage.

With this notation, we may write the chromatic polynomial as

where $0^{k}$ is taken to be 1 if $k=0$ and 0 otherwise, so that only proper colourings contribute to the sum, with all proper colourings counted once.

Suppose now that we do not penalise improper colourings so drastically, but just weight colourings according to an exponential function of the number of good edges they have. This gives the Potts model, introduced in [96] and generalising the $q=4$ case introduced by Ashkin and Teller in [2]. (See [40, §34.12]. The model is called the Ashkin-Teller-Potts model in [114, §4.4].) The Potts model partition function is given by¹¹1Sometimes, it is defined instead as $\sum_{f:V\rightarrow[q]}e^{K\cdot|E^{+}(f)|}$, which may be written $e^{K|E|}\sum_{f:V\rightarrow[q]}e^{-K\cdot|E^{-}(f)|}$. So the only change is an extra prefactor $e^{K|E|}$. See, e.g., [5, §2].

This is a polynomial in $e^{-K}$ and is known to be a partial evaluation of the Tutte polynomial [27, 46]. The relationship between them can be expressed more simply in terms of the Whitney rank generating function:

The $q=2$ case of the Potts model partition function is mathematically almost the same as the Ising model partition function [58]. In the Ising model, colours take values in $\{\pm 1\}$, and we sum over all $\{\pm 1\}$-assignments $\sigma:V\rightarrow\{\pm 1\}$. For a given $\sigma:V\rightarrow\{\pm 1\}$, the edge $uv$ belongs to the set $E^{\sigma(u)\sigma(v)}(f)$. The Ising model partition function is

The Ashkin-Teller model [2] extends the Ising model and the $q=4$ case of the Potts model. Each vertex $v\in V$ has a pair of colours $\sigma(v)$ and $\tau(v)$, each taking one of the two values $\pm 1$, so the available colour pairs $(\sigma(v),\tau(v))$ for each vertex are the four pairs $(\pm 1,\pm 1)$. We think of the $\{\pm 1\}$-assignments $\sigma:V\rightarrow\{\pm 1\}$ and $\tau:V\rightarrow\{\pm 1\}$ as two Ising spin functions on $G$. An example is given in Figure 2, where the spins at upper left and lower right of each vertex are those assigned by $\sigma$ and $\tau$, respectively. These spins are also shown as colours on the left and right semicircles in each vertex.

These yield a third such function, their product $\sigma\tau\,:\,V\rightarrow\{\pm 1\}$, given for each $v\in V$ by $(\sigma\tau)(v)=\sigma(v)\tau(v)$. So we have three Ising spin functions, coupled in the sense that they are not all independent: we can regard any two of them as independent, but together they determine the third. Each of them gives its own division of $E(G)$ into good and bad edges, so we have three such divisions altogether:

We illustrate these divisions, for the graph and configuration of Figure 2, in Figure 3.

The partition function of the symmetric Ashkin-Teller model is given by

The symmetry is because the coefficients of $|E^{-}(\sigma)|$ and $|E^{-}(\tau)|$ in the exponent are the same, namely $K$. In the general four-state Ashkin-Teller model, these can be different, and the partition function depends on three variables instead of the two ($K$, $K^{\prime}$) we have here.

If $K^{\prime}=0$ then $Z_{\hbox{\scriptsize SymAT}}(G;K,K^{\prime})$ is just the square of an Ising model partition function:

If $K=K^{\prime}$ then $Z_{\hbox{\scriptsize SymAT}}(G;K,K^{\prime})$ is just a Potts model partition function up to a simple factor:

In these two cases, the symmetric Ashkin-Teller model partition function can be obtained from the Tutte polynomial, since the Ising and Potts model partition functions can be so obtained. But this is not possible in general. Direct evaluation shows that the two Tutte equivalent Gray graphs (Figure 1) have different symmetric Ashkin-Teller model partition functions. From this we see that the symmetric Ashkin-Teller model partition function is not a specialisation of the Tutte polynomial.

We can represent any subset $X\subseteq E$ of the edge set of a graph by its characteristic vector $\mathbf{x}=(x_{e})_{e\in E}\in\hbox{GF}(2)^{E}$ defined by

A cocircuit of $G$ is a minimal set of edges whose removal does not disconnect any component of $G$. These are also the circuits of the dual of the cycle matroid of $G$. The cocircuit space of $G$ is the linear space over $\hbox{GF}(2)$ generated by the characteristic vectors of cocircuits of $G$. This is also the row space of the binary incidence matrix of $G$, which has rows indexed by $V$, columns indexed by $E$, and each entry is 1 or 0 according as its vertex is, or is not, incident with its edge.

In [29], the operations of contraction and deletion are applied directly to the indicator functions of cocircuit spaces. Let $f:2^{E}\rightarrow\{0,1\}$ be the indicator function of the cocircuit space of $G$. Let $f//e:2^{E}\rightarrow\{0,1\}$ and $f\setminus\setminus e:2^{E}\rightarrow\{0,1\}$ be the indicator functions of $G/e$ and $G\setminus e$, respectively. Then it is shown in [29] that

This is used in two related generalisations. Firstly, in [29], contraction and deletion are extended to arbitrary $f:2^{E}\rightarrow\mathbb{R}$ satisfying $f(\emptyset)=1$; in later work it was convenient to include all $f:2^{E}\rightarrow\mathbb{C}$. Such functions $f$ are called binary functions, and if $f$ is the indicator function of the cocircuit space of a graph then it is graphic. Secondly, in [32], contraction and deletion are considered to be just two specific reductions in a whole family of $\lambda$-reductions parameterised by $\lambda\in\mathbb{R}$, and later by $\lambda\in\mathbb{C}$ in [34], using the notation and expression in the middle column, where $e\in E$ and $X\subseteq E\setminus\{e\}$:

Ordinary contraction and deletion are given by $\lambda=0$ and $\lambda=1$, respectively. When $\lambda\in[0,1]$, one can think of the $\lambda$-reduction as interpolating between contraction and deletion. These $\lambda$-reductions come in dual pairs, with the dual of $\lambda$-reduction being $\lambda^{*}$-reduction where

When $\lambda\not\in\{0,1\}$, a $\lambda$-reduction of a graphic binary function is not, in general, graphic.

These dual $\lambda$-reduction operations are accompanied by parameterised versions of the rank function and Whitney rank generating function. The $\lambda$-rank function $Q^{(\lambda)}f$ is defined by

where $X\subseteq E$. The $\lambda$-Tutte-Whitney function is defined by

These functions are shown in [32] to satisfy a generalisation of the contraction-deletion relation of the same form as for Tutte-Whitney polynomials, with $\lambda$-reductions and their dual $\lambda^{*}$-reductions taking the place of contraction and deletion. The loopiness and coloopiness of the element $e\in S$ under the function $f$ are defined by the functions

János is a keen Go player. He and the first author have played several times; as the stronger player, János plays with the white stones and gives a handicap. So it is fitting to mention some surprising points of contact between graph polynomials and the theory of Go.

Here we use the name by which the game is known in Japan and in the West. It is called Wéiqí in China and Baduk in Korea.

Go is normally played on the square grid graph of $19\times 19$ vertices. But it has long been recognised that Go is an entirely graph-theoretic game and can be played on any graph. It has been played, for example, on a three-dimensional diamond lattice graph [98] and on a map of Milton Keynes [57].

Thorpe and Walden [101, 102] seem to have been among the first to formalise the rules and concepts of Go in order to support mathematical and computational investigation. Their work uses some graph-theoretic concepts but is still embedded in rectangular grid graphs. Benson [6] uses graph-theoretic language and concepts to characterise unconditional life of groups of stones. Tromp and Taylor [105, 99] defined “logical rules” for Go, based on rules from the New Zealand Go Society. These rules are concise, precise, elegant, and purely graph-theoretic. Although they state initially that Go is played on a $19\times 19$ square grid, these rules may be used with only cosmetic modifications to play on any graph.

Let $G$ be a graph and $f$ be a partial $\lambda$-assignment of $G$. A chromon of $(G,f)$ is free if it has a vertex that is adjacent to an uncoloured vertex. A partial $\lambda$-assignment $f$ is a legal $\lambda$-position in $G$, or just a legal position if $\lambda$ is clear from the context, if every chromon is free.

Normally, Go is played with just two colours, Black and White, so $\lambda=2$, although multiplayer versions with $\lambda>2$ have been proposed and equipment (in the form of coloured Go stones) is available for them.

In Go terminology, chromons correspond to what a Go player might call chains. A chromon is free if it is a chain with at least one liberty, and a legal position is one in which every chain has a liberty. When playing the game according to the rules, every position will be a legal position except during the brief intervals after a capture is made and before all the captured stones are removed from the board. We do not discuss the rules of Go further; see, e.g., [59] for more information.

Two Go polynomials based on these concepts were introduced in [31], studied further in [42, 36, 39], and mentioned by János in his first inventory of the Zoo [69, 70]. One of them simply counts legal positions:

For example, it can be shown that $\hbox{\rm Go}^{\#}(C_{4};\lambda)=1+14\lambda^{2}$. The other Go polynomial from [31] is based on a simple probability model. Let $p\leq\frac{1}{2}$ and construct a random partial 2-assignment $f$ as follows. Each $v\in V$ is assigned colour 1 or 2, with probability $p$ each, or is left uncoloured with probability $r:=1-2p$, with decisions for different vertices being independent. Under this model, define

We could also define a bivariate version of the second polynomial by extending the probability model to $\lambda$ colours, where $f$ is now a partial $\lambda$-assignment, the probability $p$ now satisfies $p\leq\lambda^{-1}$, and $f$ is assigned colour $k\in[\lambda]$ with probability $p$ for each colour and is left uncoloured with probability $r:=1-\lambda p$:

All three functions can be shown to be polynomials, so they can take as arguments any $\lambda,p\in\mathbb{C}$ although we only know of combinatorial interpretations for the values used in the definitions above. This suggests the problem of finding combinatorial interpretations at other values of $p$ and $\lambda$. We suggest $\lambda=-1$ as one that might be worth exploring, since the chromatic polynomial has an interesting combinatorial interpretation at $\lambda=-1$, namely the number of acyclic orientations [100], and Go polynomials can be expressed naturally as sums of chromatic polynomials [31].

These Go polynomials are all exponential-time computable, and they seem unlikely to be polynomial-time computable because it was shown in [31, §4] that, for any fixed integer $\lambda\geq 2$, computing the value of $\hbox{\rm Go}^{\#}(G;\lambda)$ for an input graph $G$ is #P-hard, using methods from transcendental number theory.

Given a graph $G$, a nonnegative integer $\lambda$ representing some number of available colours, and a probability $p\leq\lambda^{-1}$, put $r:=1-\lambda p$ and define the following random colouring model, noting that the partial $\lambda$-assignment it produces is not necessarily a (proper) colouring.

Each vertex $v\in V(G)$ remains uncoloured with probability $r$ and otherwise is given a colour chosen uniformly at random from the $\lambda$ available colours. So, for any specific colour, the probability that $v$ gets that colour is $p$. The choices made at different vertices are independent. This process generates a random partial $\lambda$-assignment whose domain is a subset of $V(G)$.

A partial $\lambda$-assignment $f$ of $G$ is a partial $\lambda$-colouring if it is a colouring of $G[\mathop{\mathrm{dom}}f]$, the subgraph of $G$ induced by the coloured vertices. In a partial $\lambda$-colouring, vertices that are adjacent in $G$ cannot both get the same colour; either they receive different colours or at least one of them is uncoloured.

We say $f$ is $\lambda$-extendable if there is a $\lambda$-colouring of $G$ that extends $f$.

A vertex $v\not\in\mathop{\mathrm{dom}}f$ is immediately $\lambda$-forced by $f$ if its neighbours in $\mathop{\mathrm{dom}}f$ have exactly $\lambda-1$ distinct colours among them, and in this case we write $f;v$ for the partial $\lambda$-assignment on $(\mathop{\mathrm{dom}}f)\cup\{v\}$ which agrees with $f$ on $\mathop{\mathrm{dom}}f$ and gives $v$ the sole colour from $[\lambda]$ that does not appear among its neighbours. The motivation is that, if vertex $v$ is to receive a colour from $[\lambda]$ without creating any bad edges, then it must be given that one colour that is unused by any of its neighbours. If the number of different colours that appear among the neighbours of $v$ is $\lambda$, then there is no hope for $v$: any colouring of it creates one or more bad edges. If the neighbours of $v$ only have $\leq\lambda-2$ colours, then the colour of $v$ is not determined by the colours of its neighbours, as there are at least two options for it.

If $f$ immediately $\lambda$-forces $v$, then there is only one possible colour for $v$ in all $\lambda$-colourings of $G$ that extend $f$. But the converse does not hold in general: the colour of $v$ may be uniquely determined without being forced in this specific local sense.

The vertex $v$ is (eventually) $\lambda$-forced by $f$ if there is a sequence of vertices $v_{1},\ldots,v_{k}=v$, all outside $\mathop{\mathrm{dom}}f$, and a sequence of partial $\lambda$-assignments $f=f_{0},f_{1},\ldots,f_{k}$ such that, for all $i\in[\lambda]$,

• •

  $\mathop{\mathrm{dom}}f_{i}=(\mathop{\mathrm{dom}}f)\cup\{v_{1},\ldots,v_{i}\}$,

• •

  $v_{i}$ is immediately forced by $f_{i-1}$,

• •

  $f_{i}=f_{i-1};v_{i}$.

We may drop $\lambda$ from “$\lambda$-forced” when it is clear from the context.

Note that if $f$ is improper then it is not $\lambda$-extendable, and that if $f$ is not $\lambda$-extendable then (regardless of whether or not it is proper) it cannot force a $\lambda$-colouring of $G$.

For every graph $G$ we define three bivariate functions based on partial colourings.

The partial chromatic polynomial $\hbox{PC}(G;p,\lambda)$ is defined by

where $p\in[0,\lambda^{-1}]$ is the probability that a specific vertex gets a particular colour, and $\lambda\in\mathbb{N}$. Since $\hbox{PC}(G;p,\lambda)$ is a polynomial (as we will shortly see), its domain is $\mathbb{C}^{2}$. Observe that $\hbox{PC}(G;\lambda^{-1},\lambda)=\lambda^{-n}P(G;\lambda)$ and $\hbox{PC}(G;0,\lambda)=1$. The partial chromatic polynomial is a simple algebraic transformation of the generalised chromatic polynomial $P(G;x,y)$ introduced by [22]. For $x\in\mathbb{N}$ and $y\in[x]$, the value of $P(G;x,y)$ is the number of $[x]$-assignments for which the first $y$ colour classes are proper. If we divide by the total number $x^{n}$ of all $[x]$-assignments, then this falls within the random partial colouring framework by putting $p=x^{-1}$, $\lambda=y$ and $r=1-x^{-1}y$. So we have

The change of variables is easily inverted to obtain

By considering all possibilities for the domain of $f$, we obtain

which is just a rearrangement of [22, Theorem 1] and shows that $\hbox{PC}(G;p,\lambda)$ is indeed a polynomial. When $\lambda$ is fixed, we denote the resulting polynomial in $p$ by $\hbox{PC}_{\lambda}(G;p)$.

The partial chromatic polynomial is also a specialisation of some trivariate graph polynomials that count edge-subsets according to $(|X|,\nu(X),\kappa(X))$ or according to simple invertible transformations of them, e.g., $(|X|,\nu(X),\rho(X))$. Historically, the first of these trivariate polynomials seems to have been the Borzacchini-Pulito polynomial [11], given by

They gave a ternary reduction relation for it in [11, Theorem 2]. Averbouch, Godlin and Makowsky [3, 4] introduced the edge elimination polynomial $\xi(G;x,y,z)$ as the most general trivariate graph polynomial that satisfies a ternary reduction relation using edge deletion, contraction and extraction (deletion of an edge, its endpoints and their incident edges) and showed how to express it as a sum over pairs of disjoint subsets of edges. Trinks [104] showed that these two trivariate polynomials are equivalent in the sense that each can be transformed to the other by simple transformations of the variables.

The extendable colouring function is given by

Observe that $\hbox{EC}(G;\lambda^{-1},\lambda)=\lambda^{-n}P(G;\lambda)$ and $\hbox{EC}(G;0,\lambda)$ is 1 if $G$ is 3-colourable and 0 otherwise. We can express $\hbox{EC}(G;p,\lambda)$ as a sum over all possible domains for $f$,

where $\hbox{EC}(G,C;\lambda)$ is the number of partial $\lambda$-colourings $f$ such that $\mathop{\mathrm{dom}}f=C$ and $f$ has an extension which is a $\lambda$-colouring of $G$. But this does not show that $\hbox{EC}(G;p,\lambda)$ is a polynomial. In fact, in general it is not. Consider $K_{2}$.

It follows from (3) that $\hbox{EC}(K_{2};p,\lambda)$ is not a polynomial, since when $p=0$ it is 1 for every positive integer $\lambda\geq 2$ but is 0 for $\lambda=1$, a property that no polynomial can have. Nonetheless, $\hbox{EC}(G;p,\lambda)$ is a polynomial in $p$ for every fixed $\lambda\in\mathbb{N}$. When $\lambda$ is fixed, we denote this polynomial in $p$ by $\hbox{EC}_{\lambda}(G;p)$.

For the extendable colouring polynomial $\hbox{EC}_{\lambda}(G;p)$, even checking the structures being counted seems hard in general for $\lambda\geq 3$. Testing whether a given partial $\lambda$-assignment of a given graph $G$ is extendable to a $\lambda$-colouring of $G$ is NP-complete when $\lambda\geq 3$, by polynomial-time reduction from graph $\lambda$-colourability: when the partial $\lambda$-assignment is the empty $\lambda$-assignment, leaving all vertices uncoloured, we just have standard $\lambda$-colourability. So this polynomial is likely to be more difficult to work with than many that have been studied.

The forced colouring function is given by

Again, we have $\hbox{FC}(G;\lambda^{-1},\lambda)=\lambda^{-n}P(G;\lambda)$. We can express $\hbox{FC}(G;p,\lambda)$ as a sum,

where $\hbox{FC}(G,C;\lambda)$ is the number of partial $\lambda$-colourings $f$ such that $\mathop{\mathrm{dom}}f=C$ and $f$ eventually forces a $\lambda$-colouring of $G$. But, again, we do not have a polynomial, in general. Consider a null graph.

This is because when there is only one colour, the colour of every initially-uncoloured isolated vertex is forced, while if there are at least two colours, an uncoloured isolated vertex cannot be forced, so it can only get a colour from the initial random partial colouring. It follows from (4) that $\hbox{FC}(\overline{K_{n}};p,\lambda)$ is not a polynomial, since when $p=0$ it is zero for every positive integer $\lambda\geq 2$ but is 1 for $\lambda=1$. But $\hbox{FC}(G;p,\lambda)$ is a polynomial in $p$ for every fixed $\lambda\in\mathbb{N}$, denoted by $\hbox{FC}_{\lambda}(G;p)$.

Our three bivariate functions satisfy

whenever $\lambda\in\mathbb{N}$ and $0\leq p\leq\lambda^{-1}$.

For these three functions, the case $\lambda=3$ is of particular interest:

We are particularly interested in $\hbox{FC}_{3}(G;p)$ which we call the forced 3-colouring polynomial of $G$. We list some basic examples and observations.

In many graph polynomials, the structures being counted can be checked very quickly in parallel. Typically, these checking problems belong to the class NC of decision problems solvable by uniform families of logical circuits of polynomial size and polylogarithmic depth, both of these being upper bounds in terms of the input size. (See, e.g., [51] for the theory of NC and P-completeness.) For example, validity of a particular 3-colouring, or an independent set, or a clique, is just a conjunction of local conditions based on the edges of the graph; validity of a flow or a matching or a dominating set is a conjunction of local conditions based on the vertex neighbourhoods.

One motivation for studying the forced 3-colouring polynomial is because of the computational complexity of checking the structures being counted, i.e., checking if a partial 3-assignment forces a 3-colouring of the graph. This can be done in polynomial time, so the situation is not as bad as for extendable colouring polynomials, and may seem more akin to classical graph polynomials based on enumerating structures like colourings, independent sets, matchings and so on. But the forced 3-colouring polynomial has the distinctive feature that its checking problem is, in a precise sense, as hard as any problem in P. Specifically, it is logspace-complete for P [30], which is considered to be evidence that there is no fast parallel algorithm for this test and that it does not belong to NC. Intuitively, this may make these graph polynomials more difficult to compute and to investigate than the many others where the structure-checking can be done in NC. So the study of them might shed light on some less-explored regions of the theory of graph polynomials.

The forced 3-colouring polynomial does fall within the class of SOL-definable graph polynomials, introduced by Makowsky and colleagues [67, 70] and explained in more detail in [48, 60]. To see this, we can express it as