# On the Complexity of
Generalized Chromatic Polynomials

A. Goodall111Supported by the Heilbronn Institute for Mathematical Research,
Bristol, UK<EMAIL_ADDRESS>[ M. Hermann222Work done in part while
the authors were visiting the Simons Institute for the Theory of Computing in
Spring 2016<EMAIL_ADDRESS>[ T. Kotek333Supported by the
Austrian National Research Network S11403- N23 (RiSE) of the Austrian Science
Fund (FWF<EMAIL_ADDRESS>[ J.A. Makowsky444Work done in part while the
authors were visiting the Simons Institute for the Theory of Computing in
Spring 2016<EMAIL_ADDRESS>[ S.D. Noble555Supported by the Heilbronn
Institute for Mathematical Research, Bristol, UK<EMAIL_ADDRESS>[ IUUK,
MFF, Charles University, Prague, Czech Republic  LIX (CNRS, UMR 7161), École
Polytechnique, 91128 Palaiseau, France  Technische Universität Wien, Institut
für Informationssysteme, 1040 Wien, Austria  Department of Computer Science,
Technion–IIT, 32000 Haifa, Israel  Department of Economics, Mathematics and
Statistics, Birkbeck, University of London, London,
United Kingdom

###### Abstract

J. Makowsky and B. Zilber (2004) showed that many variations of graph
colorings, called $\mathbf{CP}$-colorings in the sequel, give rise to graph
polynomials. This is true in particular for harmonious colorings, convex
colorings, $mcc_{t}$-colorings, and rainbow colorings, and many more. N.
Linial (1986) showed that the chromatic polynomial $\chi(G;X)$ is
$\\#{\mathbf{P}}$-hard to evaluate for all but three values $X=0,1,2$, where
evaluation is in ${\mathbf{P}}$.

This dichotomy includes evaluation at real or complex values, and has the
further property that the set of points for which evaluation is in P is
finite. We investigate how the complexity of evaluating univariate graph
polynomials that arise from $\mathbf{CP}$-colorings varies for different
evaluation points. We show that for some $\mathbf{CP}$-colorings (harmonious,
convex) the complexity of evaluation follows a similar pattern to the
chromatic polynomial. However, in other cases (proper edge colorings,
$mcc_{t}$-colorings, $H$-free colorings) we could only obtain a dichotomy for
evaluations at non-negative integer points. We also discuss some
$\mathbf{CP}$-colorings where we only have very partial results.

###### keywords:

Graph polynomials , Counting Complexity , Chromatic Polynomial,

url]http://kam.mff.cuni.cz/ andrew

url]http://www.lix.polytechnique.fr/Labo/Miki.Hermann

url]http://forsyte.at/ kotek/

url]http://www.cs.technion.ac.il/ janos

url]http://www.bbk.ac.uk/ems/faculty/steven-noble

###### Contents

  1. 1 Introduction
    1. 1.1 The complexity spectrum
    2. 1.2 Easy computation of the polynomial versus its easy evaluation
    3. 1.3 Linial’s Trick
    4. 1.4 The Difficult Point Dichotomy
  2. 2 One, two, many chromatic polynomials
    1. 2.1 Many chromatic polynomials
    2. 2.2 $\mathcal{P}$-colorings and variations
  3. 3 Detailed case study: Dichotomy theorems
    1. 3.1 Harmonious colorings
    2. 3.2 Convex colorings
    3. 3.3 $DU(H)$-colorings
  4. 4 Counting convex colorings is $\\#{\mathbf{P}}$-complete: the proof
    1. 4.1 Cuts, crossing sets, and cocircuits
    2. 4.2 Reductions
  5. 5 Detailed case study: Discrete spectra
    1. 5.1 Proper edge colorings
    2. 5.2 $mcc_{t}$-colorings
    3. 5.3 $H$-free-colorings
  6. 6 More graph polynomials
    1. 6.1 Graph polynomials with incomplete complexity spectrum
    2. 6.2 ${\mathbf{NP}}$-hardness
  7. 7 Conclusions and open problems

##  1 Introduction

By a classical result of R. Ladner, and its generalization by K. Ambos-Spies,
[41, 6], there are infinitely many degrees (via polynomial time reducibility)
between ${\mathbf{P}}$ and ${\mathbf{NP}}$, and between ${\mathbf{P}}$ and
$\\#{\mathbf{P}}$, provided ${\mathbf{P}}\neq{\mathbf{NP}}$. In contrast to
this, the complexity of evaluating partition functions or counting graph
homomorphisms satisfies a dichotomy theorem: either evaluation is in
${\mathbf{P}}$ or it is $\\#{\mathbf{P}}$-complete, [21, 9, 13]. For the
definition of the complexity class $\\#{\mathbf{P}}$, see [27] or [50].

In accordance with the literature in graph theory a finite graph
$G=(V(G),E(G))$ with $n(G)=|V(G)|$ and $e(G)=|E(G)|$ has order $n(G)$ and size
$e(G)$. Otherwise, the size of a finite set is its cardinality.

In this paper we study the complexity of the evaluation of generalized
univariate chromatic polynomials, as introduced in [49] and further studied in
[37, 38]. They will be called in the sequel $\mathbf{CP}$-colorings (for
Counting Polynomials). Among these we find:

######  Examples 1.1.

  1. (i)

Trivial (unrestricted) vertex colorings using at most $k$ colors are just
functions $V(G)\rightarrow[k]$. We denote by $\chi_{trivial}(G;k)$ the number
of trivial colorings of $G$, hence
$\chi_{trivial}(G;k)=k^{|V(G)|}\in{\mathbb{Z}}[k]$.

  2. (ii)

Proper vertex colorings using at most $k$ colors, where two neighboring
vertices receive different colors, are counted by $\chi(G;k)$, the classical
chromatic polynomial .

  3. (iii)

Proper edge colorings using at most $k$ colors, where two edges with a common
vertex receive different colors, are counted by $\chi_{edge}(G;k)$, the edge
chromatic polynomial. We note that they are exactly the proper vertex
colorings of the line graph $L(G)$ of $G$.

  4. (iv)

Convex colorings using at most $k$ colors are vertex colorings, which are not
necessarily proper, but where each color class induces a connected subgraph.
They are counted by $\chi_{convex}(G;k)$. Convex colorings are first
introduced in [48].

  5. (v)

Harmonious colorings using at most $k$ colors are proper vertex colorings such
that no two edges have end-vertices receiving the same pair of colors. They
were introduced in [32, 25, 23]. We denote the number of harmonious colorings
using at most $k$ colors by $\chi_{harm}(G;k)$. The graph parameter
$\chi_{harm}(G;X)$ is a polynomial in $k$ by [49, 38] which was further
studied more recently in [20].

  6. (vi)

For a fixed connected graph $H$, $DU(H)$-colorings are vertex colorings, where
each color class induces a disjoint collection of copies of $H$. The graph
parameter counting the number of $DU(H)$-colorings with at most $k$ colors is
a polynomial in $k$, and the corresponding graph polynomial is denoted by
$\chi_{DU(H)}(G;k)$.

  7. (vii)

For a fixed $t\in{\mathbb{N}}^{+}$, an $mcc_{t}$-coloring using at most $k$
colors is a vertex coloring, where the connected components of the subgraphs
induced by each color class have at most $t$ vertices. They were previously
studied in [3] and [43]. The graph parameter $\chi_{mcc_{t}}(G;k)$ counting
the number of $mcc_{t}$-colorings with at most $k$ colors is also a polynomial
in $k$ but not in $t$.

  8. (viii)

For a fixed graph $H$, an $H$-free coloring using at most $k$ colors is a
vertex coloring in which every color class induces an $H$-free graph. For
$H=K_{2}$ these are the proper vertex colorings. The graph parameter
$\chi_{H-free}(G;k)$ counting the number of $H$free colorings with at most $k$
colors is also a polynomial in $k$.

More examples are presented in Section 2, where we also discuss a general
theorem which allows us to find infinitely many generalized chromatic
polynomials, and in Section 6.

###  1.1 The complexity spectrum

Let ${\mathbf{F}}$ be a fixed field that contains ${\mathbb{Q}}$, the rational
numbers, and in which the arithmetic operations are polynomial time
computable. For our discussion we use the unit-cost666 If instead we use the
binary cost model for computations in, say, ${\mathbb{Q}}$, the main results
still hold, but have to be formulated more carefully, as $a\in{\mathbb{Q}}$
could be very large, and the notion of uniformity would be affected.  model
for the field computations in ${\mathbf{F}}$.

Given a graph polynomial $P(G;X)\in{\mathbf{F}}[X]$ and an element
$a\in{\mathbf{F}}$, we view $P_{a}(G)=P(G;a)$ as a graph parameter. We will
look at the complexity of the problem of evaluating $P(G;a)$ for a fixed
$a\in{\mathbf{F}}$ and at the problem of computing all the coefficients of
$P(G;X)$.

  * Problem: $P(G;a)$
Input: Graph $G$.
Output: The value of $P(G;X)$ for $X=a$.

  * Problem: $P(G;X)$
Input: Graph $G$.
Output: All the coefficients of $P(G;X)$ as a vector over ${\mathbf{F}}$.

We denote by $T_{P_{a}}(n)$ the time needed to compute $P(G;a)$ on graphs with
$n$ vertices in the Turing model of computation. Similarly $T_{P_{X}}(n)$
denotes the time needed to compute all the coefficients of $P(G;X)$. Clearly,
for every $a\in{\mathbf{F}}$ the problem $P(G;a)$ is reducible to computing
the coefficients of $P(G;X)$. The converse is not true in general, but we
shall see cases where for certain $a_{0}\in{\mathbf{F}}$ computing the
coefficients of $P(G;X)$ is reducible to $P(G;a_{0})$. When we speak
informally of the complexity spectrum of $P(G;X)$ we have in mind the
variability of $T_{P_{a}}(n)$ where $a\in{\mathbf{F}}$, without giving the
term a precise definition. For a graph polynomial $P(G;X)$, we are interested
in describing the complexity of $P_{a}(G)$ for all $a\in{\mathbf{F}}$. A more
modest task would be to describe it only for $a\in{\mathbb{N}}$. In the case
of $a\in{\mathbb{N}}$ we speak of the discrete complexity spectrum, in the
case of $a\in{\mathbf{F}}$ we speak of the full complexity spectrum, if the
context requires it.

We define

$\mathrm{EASY}(P)=\\{a\in{\mathbf{F}}:\mbox{ there exists
}d\in{\mathbb{N}}\mbox{ with }T_{P_{a}}(n)\leq n^{d}\mbox{ for all }n\geq
2\\}$

Analogously, we define

$\mathrm{\\#PHARD}(P)=\\{a\in{\mathbf{F}}:P_{a}(G)\mbox{ is
}\\#{\mathbf{P}}\mbox{-hard}\\}.$

###  1.2 Easy computation of the polynomial versus its easy evaluation

In the definition of $\mathrm{EASY}(P)$, we require that the evaluation at
$a\in{\mathbf{F}}$ takes polynomial time, but the exponent $d$ may depend on
$a$, which is to say the polynomial bound for evaluating $P(G;a)$ is non-
uniform.

If we could compute all of the coefficients of $P(G;X)$ in polynomial time, we
could also evaluate $P(G;a)$ for every $a$ in polynomial time $O(n^{d})$ where
$d$ is independent of $a$, and $P(G;a)$ can be evaluated in polynomial time
uniformly.

However, $\mathrm{EASY}(P)$ is infinite with a non-uniform polynomial bound,
then it does not follow that there exists $d$ such that for every $G$ the
coefficients of $P(G;X)$ maybe computed in time $O(n^{d})$.

######  Proposition 1.2.

  1. (i)

If the coefficients of the polynomial $P(G;X)$ can be computed in polynomial
time from $G$ alone, then $\mathrm{EASY}(P)={\mathbf{F}}$.

  2. (ii)

If, in addition to (i), there is $a\in{\mathbf{F}}$ such that
$a\in\mathrm{\\#PHARD}(P)$, then ${\mathbf{P}}=\\#{\mathbf{P}}$.

###### Proof.

As all the coefficients of $P(G;X)$ can be computed together in polynomial
time, the degree $\delta=\delta(G)$ of $P(G;X)$ is polynomial in the number of
vertices of $G$, and so is the size of the coefficients.

Evaluating such a polynomial can be done in polynomial time in the order of
$G$. Therefore if $a\in\mathrm{EASY}(P)\cap\mathrm{\\#PHARD}(P)$ we have
${\mathbf{P}}=\\#{\mathbf{P}}$. ∎

The characteristic polynomial $p_{A}(G;X)$ of a graph $G$ is the
characteristic polynomial of its adjacency matrix. A variant of this,
$p_{L}(G;X)$, is obtained by replacing the adjacency matrix by the Laplacian
of $G$. Both are obtained by computing a determinant, therefore evaluating
both $p_{A}(G;X)$ and $p_{L}(G;X)$ can be done in time $O(n^{3})$,
irrespective of the evaluation point $X=a\in{\mathbf{F}}$. Hence
$\mathrm{EASY}(p_{A}(G;X))={\mathbf{F}}$
($\mathrm{EASY}(p_{L}(G;X))={\mathbf{F}}$) uniformly.

In Section 3.1 we shall see an example where $\mathrm{EASY}(P)={\mathbb{N}}$
non-uniformly.

###  1.3 Linial’s Trick

In the case of the chromatic polynomial $\chi(G;X)$, N. Linial set the
paradigm in the following theorem:

######  Theorem 1.3 ([42]).

$\mathrm{\\#PHARD}(\chi)={\mathbf{F}}-\\{0,1,2\\}$ and
$\mathrm{EASY}(\chi)=\\{0,1,2\\}$.

To show this N. Linial observed the following:

######  Lemma 1.4 (Linial’s Trick).

Let $G_{1}\bowtie G_{2}$ be the join of the graphs $G_{1}$ and $G_{2}$,
obtained from the disjoint union $G_{1}\sqcup G_{2}$ by connecting all the
vertices of $G_{1}$ with all the vertices of $G_{2}$.

  1. (i)

A function $f:V(G\bowtie K_{1})\rightarrow[k]$ is a proper coloring with $k$
colors if and only if there is a function
$g:V(G)\rightarrow\\{1,\ldots,i-1,i+1,\ldots,k\\}$ which is a proper coloring
of $G$ with $k-1$ colors and $f|_{V(G)}=g$, i.e., $g$ is the restriction of
$f$ to $V(G)$, and $f(u)=i$.

  2. (ii)

$\chi(G\bowtie K_{1};k)=k\cdot\chi(G;k-1)$

  3. (iii)

$\chi(G\bowtie K_{n};k)=k_{(n)}\cdot\chi(G;k-n)$ where $k_{(n)}$ is the
falling factorial:
$k_{(n)}=k(k-1)(k-2)\ldots(k-(n-1))=\frac{k!}{(n-k)!}$.

This allows one for $a\not\in{\mathbb{N}}$ to evaluate $\chi(G,a-n)$ by
computing $\chi(G\bowtie K_{n},a)$. It also shows that evaluating $\chi(G;k)$
is reducible to evaluating $\chi(G;k+1)$ for $k\geq 3$.

###### Proof of Theorem 1.3.

First one proves that $\chi(G;3)$ is $\\#{\mathbf{P}}$-complete directly, as
in [42]. For the cases $a\in{\mathbb{N}}-\\{0,1,2\\}$ one uses (ii) of
Linial’s trick iteratively to reduce the computation of $\chi(G;3)$ to the
computation of $\chi(G;a)$. For the cases $a\in{\mathbf{F}}-{\mathbb{N}}$ one
uses (iii) of Linial’s trick to compute $\chi(G;a-n)$ for $n=0,1,\dots,n(G)$.
By Lagrange interpolation the polynomial $\chi(G;X)$ is thereby determined
since the degree of $\chi(G;X)$ is $n(G)$. In particular computing $\chi(G;3)$
is polynomial time reducible to computing $\chi(G;a)$. Hence, Theorem 1.3
follows. ∎

Similarly, for the generating matching polynomial

$gm(G;X)=\sum_{M\subseteq E(G)}X^{|M|},$

we have, see [4]777 It appears that this was known as folklore, but we could
not find a suitable reference..

######  Proposition 1.5.

$\mathrm{\\#PHARD}(gm)={\mathbf{F}}-\\{0\\}$ and $\mathrm{EASY}(gm)=\\{0\\}$,

G-polynomial | $E=\mathrm{EASY}(P)$ | $\mathrm{\\#PHARD}(P)$ | $\mathrm{OTHER}$ | Reference
---|---|---|---|---
$\chi_{trivial}(G;X)$ |  $E_{trivial}={\mathbf{F}}$, u | $\emptyset$ | $\emptyset$ | trivial
$p_{A}(G;X)$ |  $E_{char}={\mathbf{F}}$, u | $\emptyset$ | $\emptyset$ | folklore
$gm(G;X)$ | $E_{match}=\\{0\\}$ | ${\mathbf{F}}-E_{match}$ | $\emptyset$ | folklore
$\chi(G;X)$ | $E_{chrom}=\\{0,1,2\\}$ | ${\mathbf{F}}-E_{chrom}$ | $\emptyset$ |  Theorem 1.3
$\chi_{harm}(G;X)$ |  $E_{harm}={\mathbb{N}}$, nu | ${\mathbf{F}}-E_{harm}$ | $\emptyset$ |  Theorem 3.2
$\chi_{convex}(G;X)$ | $E_{convex}=\\{0,1\\}$ | ${\mathbf{F}}-E_{convex}$ | $\emptyset$ |  Theorem 3.6
$\chi_{DU(K_{\alpha})}(G;X)$ | $E_{DU(K_{\alpha})}=\\{0,1\\}$ | ${\mathbf{F}}-E_{DU(K_{\alpha})}$ | $\emptyset$ |  Theorem 3.16
$\alpha\geq 2$ |  |  |  |
Table 1: Full complexity spectra, u=uniformly, nu=non-uniformly G-polynomial | $E=\mathrm{EASY}(P)$ | $\mathrm{\\#PHARD}(P)$ | $\mathrm{OTHER}$ | Reference
---|---|---|---|---
$\chi_{edge}(G;X)$ | $E_{edge}=\\{0,1\\}$ | ${\mathbb{N}}-E_{edge}$ | $\emptyset$ |  Theorem 5.2
$\chi_{mcc_{t}}(G;X)$ | $E_{mcc_{t}}=\\{0,1\\}$ | ${\mathbb{N}}-E_{mcc_{2}}$ | $\emptyset$ |  Theorem 5.8
$t\geq 2,k\geq 2$ |  |  |  |
$\chi_{H-free}(G;X)$ | $E_{H-free}=\\{0,1\\}$ | ${\mathbb{N}}-\\{0,1,2\\}$ |  $\\{2\\}$ (+) |  Theorem 5.10
Table 2: Discrete complexity spectra only, $H$ of size $2$, (+) only
${\mathbf{NP}}$-hard is known

The purpose of this paper is to study the complexity spectrum of generalized
univariate chromatic polynomials arising from $\mathbf{CP}$-colorings.

In the examples we study, the complexity spectrum is easily described with the
two sets $\mathrm{EASY}(P)$ and $\mathrm{\\#PHARD}(P)$. Our results on full
complexity spectra are summarized in Table 1. Cases where only the discrete
spectrum is understood are given in Table 2.

To get a complete description of the full complexity spectrum of $P(G;a)$, one
needs two ingredients:

  1. (i)

Enough points $a\in{\mathbb{N}}$ for which the complexity of $P_{a}(G)=P(G;a)$
is known, and

  2. (ii)

some form of reducibility between $P_{a}(G)$ and $P_{b}(G)$ for the remaining
values $a,b\in{\mathbf{F}}$.

From the literature we often, but not always, can get enough information for
(i). We give here new results for (i), namely Theorems 3.5, 3.14 and 5.6. For
(ii) we try to adapt Linial’s Trick, which in some cases is more or less
straightforward, while in other cases requires finding a new gadget as in
Theorem 3.2. A precise description of what is needed for (ii) is given in [7],
which also covers the case for multivariate graph polynomials.

###  1.4 The Difficult Point Dichotomy

We say that a univariate graph polynomial has the Difficult Point Dichotomy if

  1. (i)

for every $a\in{\mathbf{F}}$ either $a\in\mathrm{EASY}(P)$ or
$a\in\mathrm{\\#PHARD}(P)$, and

  2. (ii)

$\mathrm{EASY}(P)={\mathbf{F}}$ or $\mathrm{EASY}(P)\subseteq{\mathbb{N}}$.

In [44, 46] it is conjectured that, for every univariate graph polynomial
$P(G;X)$ definable in Second Order Logic ${\mathrm{SOL}}$, the set
$\mathrm{EASY}(P)$ is either finite or $\mathrm{EASY}(P)={\mathbf{F}}$ and
that $\mathrm{EASY}(P)\cup\mathrm{\\#PHARD}(P)={\mathbf{F}}$. In [44] the same
was also conjectured for univariate graph polynomials definable in Monadic
Second Order Logic ${\mathrm{MSOL}}$. The example of $\chi_{harm}(G;X)$ is
${\mathrm{SOL}}$-definable and therefore disproves the conjecture for
${\mathrm{SOL}}$-definable graph polynomials. However, it was shown in [35]
that $\chi_{harm}(G;X)$ is not ${\mathrm{MSOL}}$-definable. Rather than
conjecturing frivolously, we state some problems.

######  Problem 1.6.

Which univariate graph polynomials $P(G;X)$ satisfy the Difficult Point
Dichotomy?

In particular,

  1. (i)

Is it true for every ${\mathrm{MSOL}}$-definable univariate graph polynomial
$P(G;X)$?

  2. (ii)

Can one find a criterion which applies to an infinite family of univariate
graph polynomials $P(G;X)$ which are not partition functions, or which do not
count homomorphisms, and which implies the Difficult Point Dichotomy.

### Outline of the paper

In Section 2 we give a simplified proof of the result from [49] that not only
counting proper graph colorings, but counting many other graph colorings, give
rise to infinitely many generalized chromatic graph polynomials. We give many
explicit examples, and show that there are infinitely many such graph
polynomials which are mutually semantically incomparable, cf. [47, 36]. In
Sections 3 and 5 we analyze in detail the graph polynomials from Table 1 and
2. In Section 4 we give the proof that counting convex colorings with $2$
colors is $\\#{\mathbf{P}}$-complete (Theorem 3.5). In Section 6 we discuss
graph polynomials for which we have only partial results. Finally, in Section
7 we summarize our conclusions and list some open problems.

##  2 One, two, many chromatic polynomials

Let $G=(V(G),E(G))$ be a finite graph and $k\in{\mathbb{N}}^{+}$ a positive
integer. We denote the set $\\{1,\ldots,k\\}$ by $[k]$. Unless otherwise
stated all graphs are simple, i.e., loop-free and without multiple edges. A
vertex (edge) coloring $f$ with $k$ colors is a function
$f:V(G)\rightarrow[k]$ ($f:E(G)\rightarrow[k]$). The coloring $f$ is proper if
no two vertices (edges) with a common edge (vertex) have the same color.

Let $\chi(G;k)$ ($\chi_{edge}(G;k)$) denote the number of proper vertex (edge)
colorings of $G$ with $k$ colors. In 1912 G. Birkhoff [10] noticed that
$\chi(G;k)$ and $\chi_{edge}(G;k)$ are polynomials in ${\mathbb{Z}}[k]$, and
therefore can be extended to polynomials in ${\mathbb{C}}[X]$, denoted, by
abuse of notation, by $\chi(G;X)$ and $\chi_{edge}(G;X)$. Birkhoff’s proof for
$\chi(G;X)$ was based on a recurrence relation involving deletion and
contraction of edges, which was generalized and led, in its most general form,
to the Tutte polynomial. For $\chi_{edge}(G;X)$ one simply observes that

$\displaystyle\chi(L(G);X)=\chi_{edge}(G;X),$ (*)

where $L(G)$ is the line graph of $G$. Although proper edge colorings have
been studied in the literature, the polynomial $\chi_{edge}(G;X)$ has not
received wide attention, probably because of (*).

###  2.1 Many chromatic polynomials

Let $\mathcal{G}$ denote the class of all finite graphs. We introduce our
concepts for vertex colorings, but they can be straightforwardly extended to
edge colorings.

Two vertex colorings $f_{1},f_{2}:V(G)\rightarrow[k]$ are isomorphic if there
is an automorphism $\alpha:V(G)\rightarrow V(G)$ of $G$ and a permutation
$\pi:[k]\rightarrow[k]$ such that for all $v\in V(G)$

$\pi(f_{1}(v))=f_{2}(\alpha(v)).$

Let
$\mathrm{COL}=\bigcup_{G\in\mathcal{G}}\bigcup_{k\in{\mathbb{N}}^{+}}[k]^{V(G)}$.
A coloring property $\Phi$ is a subset of $\mathrm{COL}$ that is closed under
isomorphisms of colorings.

For a fixed coloring property $\Phi$, a graph $G\in\mathcal{G}$,
$k\in{\mathbb{N}}^{+}$ and $I\subseteq[k]$, let

$\chi_{\Phi}(G;k)=|\\{f\in\Phi:f:V(G)\rightarrow[k]\\}|$

and let

$c_{G}^{\Phi}(I,k)=|\\{f\in\Phi:f:V(G)\rightarrow[k]\mbox{ with
}f(V(G))=I\\}|$

be the number of colorings $f\in\Phi$ of $G$ which use exactly the colors in
$I$.

We say that $\Phi$ is a $\mathbf{CP}$-Property if the following two conditions
are satisfied:

(A)

For all $k\in{\mathbb{N}}^{+}$ and $I,J\subseteq[k]$ with $|I|=|J|=i$ we have

$c^{\Phi}_{G}(I,k)=c^{\Phi}_{G}(J,k).$

(B)

For all $k,k^{\prime}\in{\mathbb{N}}^{+}$ with $I\subseteq[k]\cap[k^{\prime}]$
we have $c^{\Phi}_{G}(I,k)=c^{\Phi}_{G}(I,k^{\prime})$.

If (A) holds we let $c^{\Phi}_{G}(i,k)$ denote the common value of
$c^{\Phi}_{G}(I,k)$, where $|I|=i$, and if both (A) and (B) hold, we let
$c^{\Phi}_{G}(i)$ denote the common value of $c^{\Phi}_{G}(i,k)$, for $k\geq
i$.

We now compute $\chi_{\Phi}(G;k)$ using (A) and (B):

$\chi_{\Phi}(G;k)=\sum_{I\subseteq[k]}c^{\Phi}_{G}(I,k)=\sum_{i}c^{\Phi}_{G}(i){k\choose
i}.$

This establishes the following result, first shown in [MZ06]:

######  Theorem 2.1 ([49]).

If $\Phi$ is a $\mathbf{CP}$-property, the counting function
$\chi_{\Phi}(G;k)$ is a polynomial in ${\mathbb{Z}}[k]$.

######  Examples 2.2.

  1. (i)

In the case of the chromatic polynomial, both (A) and (B) are satisfied. Hence
we get a new proof of Birkhoff’s Theorem.

  2. (ii)

Let $\hat{\chi}_{\Phi}(G;k)=c^{\Phi}_{G}(k)$ be the graph parameter that
counts the number of colorings in $\Phi$ of $G$ which use exactly $k$ colors.

Note that the function $\hat{\chi}_{\Phi}(G;k)$ need not be a polynomial in
$k$ when $\chi_{\Phi}(G;k)$ is a polynomial in $k$.

  3. (iii)

Let $\Phi_{1}$ be the coloring property which says $f$ is a proper coloring
with $k$ colors where all the $k$ colors are used. Here (B) is violated, and
indeed, $\chi_{\Phi_{1}}(G;k)$ is not a polynomial.

  4. (iv)

Let $\Phi_{2}$ be the coloring property which says $f$ is a proper coloring
with $k$ colors such that $f(v)=i+1$ if and only if the degree of $v$ is $i$.
Here (A) is violated, but (B) is still true, and $\chi_{\Phi_{2}}(G;k)$ is
still a polynomial.

  5. (v)

All the examples (i)-(vii) of Section 1 listed in Examples 1.1 satisfy (A) and
(B). Hence they are polynomials in $k$.

###  2.2 $\mathcal{P}$-colorings and variations

Two graph polynomials may be compared via their distinctive power. Two graphs
$G_{1}$ and $G_{2}$ are similar if they have the same number of vertices,
edges and connected components. A graph polynomial $Q(G;X)$ is less
distinctive than $P(G;Y)$, written $Q\preceq P$, if for every two similar
graphs $G_{1}$ and $G_{2}$

$\displaystyle P(G_{1};X)=P(G_{2};X)\mbox{ implies }Q(G_{1};Y)=Q(G_{2};Y).$

We also say that $P(G;X)$ determines $Q(G;X)$ if $Q\preceq P$. Two graph
polynomials $P(G;X)$ and $Q(G;Y)$ are equivalent in distinctive power
(d.p.-equivalent) if for every two similar graphs $G_{1}$ and $G_{2}$

$\displaystyle P(G_{1};X)=P(G_{2};X)\mbox{ iff }Q(G_{1};Y)=Q(G_{2};Y).$

Here we show how to obtain infinitely many graph polynomials that are mutually
incomparable in distinctive power.

Let $\mathcal{P}$ be any graph property (a class of finite graphs closed under
graph isomorphism).

A function $f:V(G)\rightarrow[k]$ is a $\mathcal{P}$-coloring if for every
$i\in[k]$ the set $f^{-1}(i)$ induces a graph $G[f^{-1}(i)]\in\mathcal{P}$.
Clearly, this is a $\mathbf{CP}$-coloring for any graph property
$\mathcal{P}$. Hence $\chi_{\mathcal{P}}(G;k)$, the number of
$\mathcal{P}$-colorings of $G$ with at most $k$ colors, is a polynomial in
$k$.

######  Theorem 2.3 ([36]).

There are infinitely many graph polynomials of the form
$\chi_{\mathcal{P}}(G;k)$ with mutually incomparable distinctive power.

We can generalize this further. Let $\mathcal{P}_{1}$ and $\mathcal{P}_{2}$ be
two graph properties. The $\mathcal{P}_{1}$-colorings such that the union of
any two color classes induces a graph in $\mathcal{P}_{2}$ form also a
$\mathbf{CP}$-property. Let

$\displaystyle\chi_{\mathcal{P}_{1},\mathcal{P}_{2}}(G;k)=$
$\displaystyle|\\{f:V(G)\to[k]:\forall_{i\in[k]}G[f^{-1}(\\{i\\})]\in\mathcal{P}_{1},\forall_{i,j\in[k],i\neq
j}G[f^{-1}(\\{i,j\\})]\in\mathcal{P}_{2}\\}|$

denote the number of such colorings. Then, for $k\in\mathbb{N}$ and a graph
$G$, the graph invariant $\chi_{\mathcal{P}_{1},\mathcal{P}_{2}}(G;k)$ is a
polynomial in $k$.

######  Problem 2.4.

For which graph properties $\mathcal{P}_{1},\mathcal{P}_{2}$ can we describe
the complexity of $\chi_{\mathcal{P}_{1},\mathcal{P}_{2}}(G;k)$? In
particular, for which graph properties does the Difficult Point Dichotomy
hold?

######  Remark 1.

In Problem 2.4 it may be reasonable to impose some complexity restrictions on
$\mathcal{P}_{1}$ and $\mathcal{P}_{2}$, e.g., we might require them to be in
${\mathbf{NP}}$.

Let $\mathcal{AH}$ be any additive induced hereditary property (closed under
taking induced subgraphs and disjoint unions). $\mathcal{AH}$-colorings have
been studied in [12, 26], in which the following is shown:

######  Theorem 2.5.

  1. (i)

([12]) There are uncountably many induced hereditary properties $\mathcal{AH}$
of graphs. Therefore, $\chi_{\mathcal{AH}}(G;k)$ may not be computable.

  2. (ii)

([26]) $\chi_{\mathcal{AH}}(G;k)$ is ${\mathbf{NP}}$-hard, unless
$\mathcal{AH}$ is the class of empty (=edgeless) graphs.

Table 3 unifies the $\mathbf{CP}$-colorings considered in Table 1 as
$\mathcal{P}_{1}$-colorings such that the union of any two color classes
induces a graph in $\mathcal{P}_{2}$. Table 3 also contains the definitions of
acyclic colorings, $t$-improper colorings and co-colorings, which will be
discussed in Section 6.

$\mathbf{CP}$-coloring | $\mathcal{P}_{1}$ | $\mathcal{P}_{2}$
---|---|---
trivial | all graphs | all graphs
proper | edgeless graphs | all graphs
acyclic | edgeless graphs | forests
convex | connected graphs | all graphs
harmonious | edgeless graphs | at most one edge
${\rm mcc}_{t}$ | conn. cpts size $\leq t$ | all graphs
$DU(H)$ | disjoint union of $\cong H$ | all graphs
$t$-imp | max. degree $t$ | all graphs
co-coloring | clique or edgeless | all graphs
$\mathcal{AH}$-coloring | $\mathcal{AH}$ | all graphs
Table 3: $\mathcal{P}_{1}$-colorings where the union of any two color classes
is in $\mathcal{P}_{2}$. In the last line $\mathcal{P}_{1}$ is an additive
induced hereditary property (closed under taking induced subgraphs and
disjoint unions).

##  3 Detailed case study: Dichotomy theorems

###  3.1 Harmonious colorings

Recall that a coloring is harmonious if it is a proper vertex coloring and
every pair of colors occurs along some edge at most once, and
$\chi_{harm}(G;X)$ is the corresponding graph polynomial.

######  Proposition 3.1.

For every $k\in{\mathbb{N}}$ there is a polynomial time Turing machine $T(k)$
which computes $\chi_{harm}(-;k)$. In other words
${\mathbb{N}}\subseteq\mathrm{EASY}(\chi_{harm})$ non-uniformly.

###### Proof.

For $X=k$ a positive integer and a graph $G$ on $n$ vertices,
$\chi_{harm}(G;k)\neq 0$ implies that $G$ has at most $e(k)={k\choose 2}$
edges. Furthermore, there are $k^{2\cdot e(k)}$ colorings of $2\cdot e(k)$
vertices with $k$ colors. Let $i(G)$ be the number of isolated vertices of
$G$,

$T(k)$ proceeds as follows:

  1. (i)

Determine $|E(G)|$. If $|E(G)|\geq e(k)+1$ we have $\chi_{harm}(G;k)=0$.

  2. (ii)

Otherwise, we strip $G$ of all its isolated vertices to obtain $G^{\prime}$,
which has at most $2\cdot e(k)$ vertices.

  3. (iii)

We count the colorings of $G^{\prime}$ which are harmonious, i.e.,
$\chi_{harm}(G^{\prime};k)$, which takes time $t(k)$, independently of the
number of vertices of $G$.

  4. (iv)

Therefore $\chi_{harm}(G;k)=k^{i(G)}\cdot\chi_{harm}(G^{\prime};k)$.

It follows that $T(k)$ runs in time $O(n^{2})$ where the constants depend on
$k$. ∎

######  Remark 2.

In spite of the low complexity of the above algorithms, we cannot compute all
the coefficients of $\chi_{harm}(G;X)$ in polynomial time. To compute
$\chi_{harm}(G;X)$ for a graph $G$ on $n$ vertices we would have to compute
for $n+1$ values $k_{1},\dots,k_{n+1}$ of $X$ the value of the function
$\chi_{harm}(G;X)$ and then use Lagrange interpolation. However, the above
algorithm inspects $k^{2\cdot e(k)}$ colorings, which for at least one of the
values $\chi_{harm}(G;k_{i})$ is bigger than $n^{2\cdot e(n)}$. It follows
from Theorem 3.2 below that, indeed, $\chi_{harm}(G;X)$ cannot be computed in
polynomial time unless ${\mathbf{P}}=\\#{\mathbf{P}}$.

######  Theorem 3.2.

For each $a\in{\mathbf{F}}-{\mathbb{N}}$ the evaluation of $\chi_{harm}(G;a)$
is $\\#{\mathbf{P}}$-hard.

###### Proof.

Let $G$ be a graph. We form $S(G)$ in the following way (see Figure 1).
We first form $G_{1}$ using $G$ by adding a new vertex $v_{e}$ for each edge
$e=(u,v)$ of $G$. Then replace the edge $e$ by two new edges $(u,v_{e})$ and
$(v_{e},v)$.
Using $G_{1}$ we now form $S(G)$: We connect all the new vertices $v_{e}:e\in
E(G)$ of $G_{1}$ such that they form a complete graph on $|E(G)|$ vertices.

For a graph $G$ and $k\in\mathbb{N}$,

$\chi_{harm}(S(G);k+e(G))=\chi(G;k)\cdot\binom{k+e(G)}{e(G)}e(G)!,$ (1)

where $e(G)=|E(G)|$ and $\chi(G;k)$ is the chromatic polynomial of $G$
evaluated at $k$. Since Equation (1) holds for every $k\in\mathbb{N}$, it is a
polynomial identity, which can be written as follows:

$\chi_{harm}(S(G);X)=X_{(e(n))}\cdot\chi(G;X-e(G)).$ (2)

Equation (2) provides a polynomial time reduction from the coefficients of
$\chi(G;X)$ to the coefficients of $\chi_{harm}(S(G);X)$, and vice versa. In
particular, determining $\chi_{harm}(S(G);X)$ is $\\#{\mathbf{P}}$-hard. We
also see from Equation (2) that for $a\in{\mathbf{F}}-\mathbb{N}$, the graph
parameter $\chi(G;a-e(G))$ is polynomial time equivalent to the evaluation
$\chi_{harm}(S(G);a)$.

$G$ $G_{1}$ $S(G)$

Figure 1: Constructing $S(G)$ from $G$

Finally, evaluating $\chi(G;a-e(G))$ is $\\#{\mathbf{P}}$-hard for
$a\not\in\mathbb{N}$. To see this, first observe the following polynomial
identity by the multiplicativity of the chromatic polynomial over disjoint
unions:

$\begin{array}[]{l}\chi(G\sqcup K_{1,n};X\\!-\\!e(G\sqcup K_{1,n}))=\\\
\chi(K_{1,n};X\\!-\\!e(G\sqcup K_{1,n}))\cdot\chi(G;X\\!-\\!e(G\sqcup
K_{1,n}))=\\\
(X\\!-\\!e(G)\\!-\\!n)\cdot(X\\!-\\!e(G)\\!-\\!n\\!-\\!1)^{n}\cdot\chi(G;X\\!-\\!e(G)\\!-\\!n).\end{array}$
(3)

For $a\in\mathbf{F}-\mathbb{N}$, we use Equation (3) to obtain the evaluations
$\chi(G;a\\!-\\!e(G)\\!-\\!n)$ for $n=0,1,\dots,|V(G)|$ and we apply Lagrange
interpolation to compute $\chi(G;X\\!-\\!e(G))$. By Equation (2) this
determines $\chi_{harm}(S(G);X)$, which as we have seen is a
$\\#{\mathbf{P}}$-hard problem. Consequently evaluating $\chi_{harm}$ at $X=a$
is $\\#{\mathbf{P}}$-hard. ∎

######  Remark 3.

From Equation (1) we also see that, since evaluating $\chi(G;3)$ is
$\\#{\mathbf{P}}$-complete, we must indeed have non-uniform polynomial time
evaluation of $\chi_{harm}(G;X)$ at positive integer points, as stated in
Proposition 3.1.

Hence we have shown:

######  Theorem 3.3.

The Difficult Point Dichotomy is true for $\chi_{harm}(G;X)$
with $\mathrm{EASY}(\chi_{harm})={\mathbb{N}}$ non-uniformly, and
$\mathrm{\\#PHARD}(\chi_{harm})={\mathbf{F}}-{\mathbb{N}}$.

###  3.2 Convex colorings

Recall that a convex coloring of a graph $G$ is an assignment of colors to its
vertices so that for each color $c$ the subgraph of $G$ induced by the
vertices receiving color $c$ is connected888 We consider a graph with no
vertices to be connected. . The resulting graph polynomial is
$\chi_{convex}(G;X)$.

The following is easily verified:

######  Proposition 3.4.

  1. (i)

For $X=1$ we have

$\chi_{convex}(G;1)=\begin{cases}1&\mbox{if }G\mbox{ is connected}\\\
0&\mbox{else}.\end{cases}$

  2. (ii)

For $k\in{\mathbb{N}}^{+}$ we have

$\chi_{convex}(G\sqcup K_{1};k)=k\cdot\chi_{convex}(G;k-1).$

In [45], it was asked whether $\chi_{convex}(-;2)$ is $\\#{\mathbf{P}}$-hard.
The question was answered in the positive and posted in [28], but remained
unpublished. Note that the number of convex colorings using at most two colors
is equal to zero if $G$ has three or more connected components and equal to
two if $G$ has exactly two connected components. So we may restrict our
attention to connected graphs.

######  Theorem 3.5 (A. Goodall and S. Noble, [28]).

Evaluating $\chi_{convex}(G;X)$ for $X=2$ on connected graphs is
$\\#{\mathbf{P}}$-complete.

The proof is given in Section 4. Combining Proposition 3.4 and Theorem 3.5 we
get the following:

######  Theorem 3.6.

$\mathrm{EASY}(\chi_{convex})=\\{0,1\\}$ and
$\mathrm{\\#PHARD}(\chi_{convex})={\mathbf{F}}-\\{0,1\\}$.

###  3.3 $DU(H)$-colorings

Let $H$ be a fixed connected graph. A coloring $f:V(G)\rightarrow[k]$ is an
$DU(H)$-coloring with $k$ colors, if each color class induces a disjoint union
of copies of $H$. We denote by $\chi_{DU(H)}(G;k)$ the number of
$DU(H)$-colorings of $G$ with at most $k$ colors, and by
$\hat{\chi}_{DU(H)}(G;k)$ the number of $DU(H)$ colorings of $G$ with exactly
$k$ colors.

We easily verify:

######  Proposition 3.7.

  1. (i)

Being a $DU(H)$-coloring with $k$ colors is a $\mathbf{CP}$-property, hence
$\chi_{DU(H)}(G;k)$ is a polynomial in $k$. However, $\hat{\chi}_{DU(H)}(G;k)$
is not a $\mathbf{CP}$-property, and in general is not a polynomial in $k$.

  2. (ii)

$\chi_{DU(H)}(G;k)=\sum_{i=1}^{k}{k\choose i}\hat{\chi}_{DU(H)}(G;i)$.

  3. (iii)

$\chi_{DU(H)}(G;k)$ is multiplicative over disjoint unions.

  4. (iv)

For $k=1$, a graph $G$ is $DU(H)$-colorable iff $G$ is a disjoint union of
$H$s.

  5. (v)

For $n(G)\not\equiv 0\mod{n(H)}$ the polynomial $\chi_{DU(H)}(G;k)$ vanishes.

Let $v\in V(H)$. We define $\Box_{H,v}(G)$ to be the graph with vertex set
$V(G)\sqcup V(H)$, and edge set $E(G)\sqcup E(H)\sqcup V(G)\times\\{v\\}$. We
can apply Linial’s Trick, cf. Lemma 1.4, to analyze the complexity of
$\chi_{DU(H)}(G;a)$.

######  Proposition 3.8.

Let $H$ be a connected graph.

  1. (i)

$\chi_{DU(H)}(\Box_{H,v}(G);k)=k\cdot\chi_{DU(H)}(G;k-1)$.

  2. (ii)

For every $a,b\in{\mathbb{N}}$ and $b>a$, $\chi_{DU(H)}(G;a)$ is polynomial
time reducible to $\chi_{DU(H)}(G;b)$.

  3. (iii)

For every $a_{0}\in{\mathbf{F}}-{\mathbb{N}}$, computing the coefficients of
$\chi_{DU(H)}(G;X)$ is polynomial time reducible to $\chi_{DU(H)}(G;a_{0})$.

The proof is the same as in [42]. For the convenience of the reader we sketch
it here.

###### Proof.

(i) All the vertices of $V(H)$ have to be colored by the same color but
differently from the vertices in $V(G)$.
(ii) Apply (i) $b-a$ many times.
(iii) Let $G_{0}=G$, $G_{i+1}=\Box_{H,v}(G_{i})$. Using
$\chi_{DU(H)}(-;a_{0})$ we can compute $\chi_{DU(H)}(G_{i};a_{0})$ for
sufficiently many $i$’s and then use Lagrange Interpolation to compute the
coefficients of $\chi_{DU(H)}(G;X)$. ∎

Related decision and counting problems have been considered in the literature.

In the following $\alpha$ is a nonnegative integer.

  * Problem: $\mathrm{CliqueCover_{\alpha}}$
Input: Graph $G$. If $\alpha\geq 1$ then $n(G)={\alpha}\cdot m$.
Question: Can we partition $V(G)$ into sets $V_{i}$ such that each $V_{i}$
induces a clique (for $\alpha=0$) or induces a copy of $K_{\alpha}$ (for
$\alpha\geq 1$)?

  * Problem: $\\#\mathrm{CliqueCover_{\alpha}}$
Input: Graph $G$. If $\alpha\geq 1$ then $n(G)={\alpha}\cdot m$.
Output: The number of partitions of $V(G)$ into sets $V_{i}$ such that each
$V_{i}$ induces a clique (for $\alpha=0$) or induces a copy of $K_{\alpha}$
(for $\alpha\geq 1$).

We note for $\alpha=0$ this is the classical clique cover decision problem of
Richard Karp’s original 21 problems, see [27].

From the literature we know the following:

######  Theorem 3.9.

  1. (i)

$\mathrm{CliqueCover_{0}}$ is ${\mathbf{NP}}$-complete and
$\\#\mathrm{CliqueCover_{0}}$ is $\\#{\mathbf{P}}$-complete, [27, 30].

  2. (ii)

$\mathrm{CliqueCover_{1}}$ and $\\#\mathrm{CliqueCover_{1}}$ are both trivial.

  3. (iii)

$\mathrm{CliqueCover_{2}}$ is the same as finding a perfect matching, and is
in ${\mathbf{P}}$, and $\\#\mathrm{CliqueCover_{2}}$ is
$\\#{\mathbf{P}}$-complete by [52].

  4. (iv)

$\mathrm{CliqueCover_{3}}$ is ${\mathbf{NP}}$-complete and
$\\#\mathrm{CliqueCover_{3}}$ is $\\#{\mathbf{P}}$-complete, [34, 30].

######  Problem 3.10.

For which $\alpha\geq 4$ is $\\#\mathrm{CliqueCover_{\alpha}}$
$\\#{\mathbf{P}}$-complete?

The connection between $\\#\mathrm{CliqueCover_{\alpha}}$ and
$\chi_{DU(K_{\alpha})}(G;X)$ is given as follows:

######  Proposition 3.11.

  1. (i)

$\chi_{DU(K_{1})}(G;X)=\chi(G;X)$, the chromatic polynomial.

  2. (ii)

$\hat{\chi}_{DU(K_{\alpha})}(G;\frac{n}{\alpha})=\left(\frac{n}{\alpha}\right)!\cdot\\#\mathrm{CliqueCover_{\alpha}}$
where $\alpha\neq 0$ and $n(G)$ is divisible by $\alpha$.

###### Proof.

If $n=n(G)$ is divisible by $\alpha$, the maximal value $k$ such that
$\hat{\chi}_{DU(K_{\alpha})}(G;k)\neq 0$ is $k=\frac{n}{\alpha}$. In this case
the subgraph induced by each color class is isomorphic to $K_{\alpha}$, and
there are $\left(\frac{n}{\alpha}\right)!$ many such colorings. ∎

We will prove that $\chi_{DU(K_{\alpha})}(G;2)$ is $\\#{\mathbf{P}}$-hard for
every $\alpha\geq 2$ in Theorem 3.14 below by describing a polynomial time
reduction from the $\\#{\mathbf{P}}$-hard problem
$\\#\alpha\mbox{-}\mathrm{of}\mbox{-}2\alpha\mbox{-}\mathrm{SAT}$. From [17]
we know that $\\#\alpha\mbox{-}\mathrm{of}\mbox{-}2\alpha\mbox{-}\mathrm{SAT}$
is $\\#{\mathbf{P}}$-complete.

  * Problem: $\\#\alpha\mbox{-}\mathrm{of}\mbox{-}2\alpha\mbox{-}\mathrm{SAT}$
Input: $2\alpha$CNF formula $\Theta$.
Output: The number of truth assignments such that, in each clause, $\alpha$
literals are true and the other $\alpha$ are false.

Now we proceed to describe the construction of a graph $\overline{G}_{\Theta}$
for every input $\Theta$ to
$\\#\alpha\mbox{-}\mathrm{of}\mbox{-}2\alpha\mbox{-}\mathrm{SAT}$. We will
prove that
$\\#\alpha\mbox{-}\mathrm{of}\mbox{-}2\alpha\mbox{-}\mathrm{SAT}(\Theta)=\chi_{DU(K_{\alpha})}(\overline{G}_{\Theta};2)$.

Let $\Theta=\bigwedge_{i=1}^{s}C_{i}$ be a $2\alpha$CNF formula with clauses
$C_{i}=l_{i,1}\lor\cdots\lor l_{i,2\alpha}$. Without loss of generality, let
the variables which occur in $\Theta$ be $x_{t}:t\in[r]$. The literals
$l_{i,j}$ of $\Theta$ are either variables $x_{t}$ or negation of variables
$\neg x_{t}$. We define $\mathrm{var}(x_{t})=\mathrm{var}(\neg x_{t})=x_{t}$.

For every clause $C_{i}$ of $\Theta$, let $G_{i}$ be a clique of size
$2\alpha$ whose vertices are labeled by $l_{i,1},\ldots,l_{i,2\alpha}$
respectively. Let $G_{\Theta}$ be the disjoint union of $G_{i}$ for all
clauses $C_{i}$ of $\Theta$. For every variable $x_{t}:t\in[r]$ let $D_{t}$ be
a clique of size $2\alpha$ in which $\alpha$ vertices are labeled $x_{t}$ and
the other $\alpha$ vertices are labeled $\neg x_{t}$. Let $D_{\Theta}$ be the
disjoint union of $D_{t}:t\in[r]$.

We construct a graph $\overline{G}_{\Theta}$ as follows. The graph
$\overline{G}_{\Theta}$ is obtained from the disjoint union $G_{\Theta}\sqcup
D_{\Theta}$ of $G_{\Theta}$ and $D_{\Theta}$ by adding an edge between any
vertex of $G_{\Theta}$ and any vertex of $D_{\Theta}$ whose labels are
negations of each other (i.e. one is $x_{t}$ and the other is $\neg x_{t}$,
$t\in[r]$).

Any coloring $c:V(\overline{G}_{\Theta})\to[2]$ can be interpreted as
assigning the truth values true (for the color $1$) and false (for the color
$2$) to the literals labeling the vertices. A coloring $c$ of
$\overline{G}_{\Theta}$ is consistent if the truth values assigned by $c$ to
the literals induce a well-defined truth value assignment $as_{c}$ to the
variables. More precisely, $c$ is consistent if any two vertices labeled the
same (both $x_{t}$ or both $\neg x_{t}$, $t\in[r]$) have the same color and
any two vertices with opposing labels ($x_{t}$ and $\neg x_{t}$, $t\in[r]$)
have different colors.

######  Lemma 3.12.

Let $c:V(\overline{G}_{\Theta})\to[2]$ be a coloring of
$\overline{G}_{\Theta}$.

  1. (i)

If $c$ is a $DU(K_{\alpha})$-coloring, then $c$ is consistent.

  2. (ii)

If $c$ is consistent, then the following are equivalent:

    1. (ii.a)

$c$ is a $DU(K_{\alpha})$-coloring.

    2. (ii.b)

$as_{c}$ satisfies the condition of
$\\#\alpha\mbox{-}\mathrm{of}\mbox{-}2\alpha\mbox{-}\mathrm{SAT}$.

###### Proof.

For (i), we assume $c$ is a $DU(K_{\alpha})$-coloring. For all $i$ and $t$,
$G_{i}$ and $D_{t}$ are cliques of size $2\alpha$. Hence, in each of the
cliques $G_{i}$ and $D_{t}$ exactly $\alpha$ vertices are colored $1$ and the
other $\alpha$ vertices are colored $2$. As a consequence, no vertex $u$ is
adjacent to any vertex $v$ such that $c(u)=c(v)$ and $u$ and $v$ belong to
different cliques in $G_{\Theta}\sqcup D_{\Theta}$.

Let $u$ be a vertex of $G_{\Theta}$ such that $u$ is labeled by $l$ and
$\mathrm{var}(l)=x_{t}$. Since there are edges between $u$ and the $\alpha$
vertices labeled by the negation of $l$ in $D_{t}$, these $\alpha$ vertices
cannot have the color $c(u)$. As a consequence, the $\alpha$ vertices labeled
by $l$ in $D_{t}$ must have the color $c(u)$. We get that all the vertices of
$\overline{G}_{\Theta}$ labeled with $l$ receive the same color, which is
different from the color of the vertices labeled by the negation of $l$, and
we get (i). Moreover, $c$ assigns exactly $\alpha$ vertices in each $G_{i}$ to
each of the colors, which implies that $as_{c}$ assigns exactly $\alpha$ of
the literals of $C_{i}$ to true and the other $\alpha$ to false. Hence
$as_{c}$ is counted by
$\\#\alpha\mbox{-}\mathrm{of}\mbox{-}2\alpha\mbox{-}\mathrm{SAT}$, and we get
the direction (a)$\Rightarrow$(b) of (ii).

For the direction (b)$\Rightarrow$(a) of (ii), let $c$ be a consistent
coloring such that $as_{c}$ is counted by
$\\#\alpha\mbox{-}\mathrm{of}\mbox{-}2\alpha\mbox{-}\mathrm{SAT}$. We will
prove that $c$ is a $DU(K_{\alpha})$-coloring. Since $as_{c}$ is counted by
$\\#\alpha\mbox{-}\mathrm{of}\mbox{-}2\alpha\mbox{-}\mathrm{SAT}$, it assigns
true to $\alpha$ literals and false to the other $\alpha$ literals of each
clause. Hence, $c$ colors every clique $G_{i}$ so that $\alpha$ vertices
receive color $1$ and the other $\alpha$ receive color $2$. Each of the two
colors induces a clique of size $\alpha$ in $G_{i}$. Since $as_{c}$ is
consistent and $D_{t}$ consists of $\alpha$ vertices labeled by some label $l$
and $\alpha$ vertices labeled by the negation of $l$, each color class of $c$
induces a clique of size $\alpha$ in $D_{t}$. It remains to notice that, since
$c$ is consistent, any other edge of $\overline{G}_{\Theta}$ crosses between
the color classes, hence does not belong to the induced subgraph of any of the
two colors. Consequently, each of the colors induces a disjoint union of
cliques of size $\alpha$ in $\overline{G}_{\Theta}$.

∎

As a consequence of Lemma 3.12 we have
$\\#\alpha\mbox{-}\mathrm{of}\mbox{-}2\alpha\mbox{-}\mathrm{SAT}(\Theta)=\chi_{DU(K_{\alpha})}(\overline{G}_{\Theta};2)$.

From [17] we have:

######  Theorem 3.13.

For every $\alpha\geq 2$,
$\\#\alpha\mbox{-}\mathrm{of}\mbox{-}2\alpha\mbox{-}\mathrm{SAT}$ is
$\\#{\mathbf{P}}$-hard.

From Lemma 3.12 and Theorem 3.13, and using the fact that the construction of
$\overline{G}_{\Theta}$ can be done in polynomial time, we get:

######  Theorem 3.14.

For every $\alpha\geq 2$, $\chi_{DU(K_{\alpha})}(G;2)$ is
$\\#{\mathbf{P}}$-hard.

######  Proposition 3.15.

$\chi_{DU(K_{\alpha})}(G;0)$ and $\chi_{DU(K_{\alpha})}(G;1)$ are polynomial
time computable.

###### Proof.

For $X=0$, $\chi_{DU(K_{\alpha})}(G;0)$ is always $0$ and hence trivially
polynomial time computable. For $X=1$, there is exactly one coloring
$c:V(G)\to[1]$ and $c$ is a $DU(K_{\alpha})$-coloring iff $G$ is a disjoint
union of copies of $K_{\alpha}$, which can be verified in polynomial time. ∎

Putting all this together we get the full complexity spectrum for

$\chi_{DU(K_{\alpha})}(G;X)$

for $\alpha\geq 2$. Recall that $\chi_{DU(K_{1})}(G;X)=\chi(G;X)$ is the
chromatic polynomial.

######  Theorem 3.16.

For all $\alpha\geq 2$, we have
$\mathrm{EASY}(\chi_{DU(K_{\alpha})})=\\{0,1\\}$ and
$\mathrm{\\#PHARD}(\chi_{DU(K_{\alpha})})={\mathbf{F}}-\\{0,1\\}$.
Moreover, for $\alpha\geq 1$ the Difficult Point Dichotomy is true for
$\chi_{DU(K_{\alpha})}(G;X)$, as for $\alpha=1$ it includes the chromatic
polynomial.

##  4 Counting convex colorings is $\\#{\mathbf{P}}$-complete: the proof

The purpose of this section is to prove Theorem 3.5. This answers a question
originally asked in [45], whether the problem of counting the number of convex
colorings using at most two colors, i.e. computing $\chi_{convex}(-;2)$, is
$\\#$P-complete on connected graphs.

This section follows almost verbatim the preprint posted as [28].

###  4.1 Cuts, crossing sets, and cocircuits

Let $X$ and $Y$ be disjoint sets of vertices of a graph $G$. The set of edges
of $G$ that have one endpoint in $X$ and the other in $Y$ is denoted by
$\delta(X,Y)$. Given a connected graph $G$, a cut is a partition of $V(G)$
into two (non-empty) sets called its _shores_. The _crossing set_ of a cut
with shores $X$ and $Y$ is $\delta(X,Y)$. A cut is a _cocircuit_ if no proper
subset of its crossing set is the crossing set of a cut. Given a set $A$ of
edges, we denote by $G\setminus A$ the graph obtained by removing the edges in
$A$ from $G$. We will use the following observation:

######  Lemma 4.1.

Let $G$ be a connected graph. Then a cut of $G$ with crossing set $A$ is a
cocircuit if and only if $G\setminus A$ has exactly two connected components.

Note that our terminology is slightly at odds with standard usage in the sense
that the terms cut and cocircuit usually refer to what we call the crossing
set of respectively a cut and a cocircuit. Our usage prevents some cumbersome
descriptions in the proofs. We will however abuse our notation by saying that
a cut or cocircuit has size $k$ if its crossing set has size $k$.

###  4.2 Reductions

We prove Theorem 3.5 by a sequence of reductions involving the following
problems:

  * Problem: $\\#$Cocircuits
Input: Connected graph $G$.
Output: The number of cocircuits of $G$.

  * Problem: $\\#$Required Size Cocircuits
Input: Connected graph $G$, strictly positive integer $k$.
Output: The number of cocircuits of $G$ of size $k$.

  * Problem: $\\#$Max Cut
Input: Connected graph $G$, strictly positive integer $k$.
Output: The number of cuts of $G$ of size $k$.

  * Problem: $\\#$Monotone 2-SAT
Input: A Boolean formula in conjuctive normal form in which each clause
contains two variables and there are no negated literals.
Output: The number of satisfying assignments.

It is easy to see that each of these problems is a member of $\\#$P.

The following result is from Valiant’s seminal paper on $\\#$P [52].

######  Theorem 4.2.

$\\#$Monotone 2-SAT is $\\#P$-complete.

We will establish the following reductions.

  * $\\#$Monotone 2-SAT $\propto\\#$Max Cut $\propto\\#$Required Size Cocircuits
$\propto\\#$Cocircuits $\propto$ $\chi_{convex}(-;2)$

Combining Theorem 4.2 with these reductions shows that each of the five
problems that we have discussed is $\\#$P-complete. As far as we are aware,
each of these reductions is new. We have not been able to find a reference
showing that $\\#$Max Cut is $\\#P$ complete. Perhaps it is correct to
describe this result as ‘folklore’. In any case we provide a proof below. Some
similar problems, but not exactly what we consider here, are shown to be
$\\#P$ complete in [51].

######  Lemma 4.3.

$\\#$Monotone 2-SAT $\propto\\#$Max Cut.

###### Proof.

Suppose we have an instance $I$ of $\\#$Monotone 2-SAT with variables
$x_{1},\ldots,x_{n}$ and clauses $\mathcal{C}=\\{C_{1},\ldots,C_{m}\\}$. We
construct a corresponding instance $M(I)=(G,k)$ of $\\#$Max Cut by first
defining a graph $G$ with vertex set

$\\{x\\}\cup\\{x_{1},\ldots,x_{n}\\}\cup\bigcup\\{\\{c_{i,1},\ldots,c_{i,6}\\}:1\leq
i\leq m\\}$

For each clause we add nine edges to $G$. Suppose $C_{j}$ is $x_{u}\vee
x_{v}$. Then we add the edges

$xc_{j,1},c_{j,1}c_{j,2},c_{j,2}x_{u},x_{u}c_{j,3},c_{j,3}c_{j,4},c_{j,4}x_{v},x_{v}c_{j,5},c_{j,5}c_{j,6},c_{j,6}x.$

Distinct clauses correspond to pairwise edge-disjoint circuits, each of size
$9$. Now let $k=8|\mathcal{C}|$. We claim that the number of solutions of
instance $M(I)$ of #Max Cut is equal to $2^{|\mathcal{C}|}$ times the number
of satisfying assignments of $I$.

Given a solution of $I$, let $L_{1}$ be the set of variables assigned the
value true and $L_{0}$ the set of variables assigned false together with $x$.
Observe that for each clause $C_{j}=x_{u}\vee x_{v}$ there are three choices
of how to add the vertices $c_{j,1},\ldots,c_{j,6}$ to either $L_{0}$ or
$L_{1}$ so that exactly eight edges of the circuit corresponding to $C_{j}$
have one endpoint in $L_{0}$ and the other in $L_{1}$. Clearly the choices for
each clause are independent and distinct satisfying assignments result in
distinct choices of $L_{0}$ and $L_{1}$. Any of the choices of $L_{0}$ and
$L_{1}$ constructed in this way may be taken as the shores of a cut of size
$8|\mathcal{C}|$. Hence we have constructed $3^{|\mathcal{C}|}$ solutions of
$M(I)$ corresponding to each satisfying assignment of $I$.

In any graph the intersection of a set of edges forming a circuit and a
crossing set of a cut must always have even size. So in a solution of $M(I)$
each of the edge-disjoint circuits making up $G$ and corresponding to clauses
of $I$ must contribute exactly eight edges to the cut. Suppose $U$ and
$V\setminus U$ are the shores of a cut of $G$ of size $8|\mathcal{C}|$. Then
it can easily be verified that for any clause $C=x_{u}\vee x_{v}$ both $U$ and
$V\setminus U$ must contain at least one element from $\\{x_{u},x_{v},x\\}$.
So it is straightforward to see that this solution of $M(I)$ is one of those
constructed above corresponding to the satisfying assignment where a variable
is false if and only if the corresponding vertex is in the same set as $x$. ∎

######  Lemma 4.4.

$\\#$Max Cut $\propto\\#$Required Size Cocircuits.

###### Proof.

Suppose $(G,k)$ is an instance of $\\#$Max Cut. We construct an instance
$(G^{\prime},k^{\prime})$ of $\\#$Required Size Cocircuits as follows. Suppose
$G$ has $n$ vertices. To form $G^{\prime}$ add new vertices
$x,x^{\prime},x_{1},\ldots,x_{n^{2}}$ to $G$. Now add an edge from $x$ to
every other vertex of $G^{\prime}$ except $x^{\prime}$ and similarly add an
edge from $x^{\prime}$ to every other vertex of $G^{\prime}$ except $x$. Let
$k^{\prime}=n^{2}+n+k$. From each solution of the $\\#$Max Cut instance
$(G,k)$ we construct $2^{n^{2}+1}$ solutions of the $\\#$Required Size
Cocircuits instance $(G^{\prime},k^{\prime})$. Suppose $C=(U,V(G)\setminus U)$
is a solution of $(G,k)$ then we may freely choose to add
$x,x^{\prime},x_{1},\ldots,x_{n^{2}}$ to either $U$ or $V(G)\setminus U$, with
the sole proviso that $x$ and $x^{\prime}$ are not both added to the same set,
to obtain a cut in $G^{\prime}$ of size $k^{\prime}=n^{2}+n+k$. Furthermore
this cut is a cocircuit because both shores contain exactly one of $x$ and
$x^{\prime}$ and so they induce connected subgraphs.

Conversely suppose $C=(U,V(G^{\prime})\setminus U)$ is a cocircuit in
$G^{\prime}$ of size $k^{\prime}$. Consider the pair of edges incident with
$x_{j}$. Note that the partition $(x_{j},V(G^{\prime})\setminus x_{j})$ is a
cocircuit. So if both of the edges incident with $x_{j}$ are in the crossing
set of $C$ then because of its minimality we must have
$C=(x_{j},V(G^{\prime})\setminus x_{j})$ which is not possible because $C$
would then have size $2<k^{\prime}$. Now suppose that neither edge incident
with $x_{j}$ is in the crossing set of $C$.

Then both $x$ and $x^{\prime}$, and hence $x_{1},\ldots,x_{n^{2}}$, lie in the
same block of the partition constituting $C$. But since $G$ is a simple graph,
the maximum possible size of such a cocircuit is at most
$2n+\binom{n}{2}<n^{2}+n+k$. Hence precisely one of the edges adjacent to
$x_{j}$ is in the crossing set. So $x$ and $x^{\prime}$ are in different
shores of $C$. Hence the crossing set of $C$ contains: for each $j$ precisely
one edge incident to $x_{j}$ ($n^{2}$ edges in total), for each $v\in V(G)$
precisely one of edges $vx$ and $vx^{\prime}$ ($n$ edges in total) and $k$
other edges with both endpoints in $V(G)$. So the partition $C^{\prime}=(U\cap
V(G),V(G)\setminus U)$ is a cut of $G$ of size $k$ and hence $C$ is one of the
cocircuits constructed in the first part of the proof. Consequently the number
of solutions of the instance $(G^{\prime},k^{\prime})$ of $\\#$Required Size
Cocircuits is $2^{n^{2}+1}$ multiplied by the number of solutions of the
instance $(G,k)$ of $\\#$Max Cut ∎

######  Lemma 4.5.

$\\#$Required Size Cocircuits $\propto\\#$Cocircuits

###### Proof.

Given a graph $G$ let $N_{k}(G)$ denote the number of cocircuits of size $k$
and $N(G)$ denote the total number of cocircuits. Let $G_{l}$ denote the
$l$-stretch of $G$, that is, the graph formed from $G$ by replacing each edge
of $G$ by a path with $l$ edges. Let $m=|E(G)|$. Then we claim that

$N(G_{l})=\sum_{k=1}^{m}l^{k}N_{k}(G)+\binom{l}{2}m.$

To see this, suppose that $C$ is a cocircuit of $G_{l}$. If the crossing set
of $C$ contains two edges from one of the paths corresponding to an edge of
$G$ then by the minimality of the crossing set of $C$ we see that it contains
precisely these two edges. The number of such cocircuits is $\binom{l}{2}m$.

Otherwise the crossing set $C$ contains at most one edge from each path in
$G_{l}$ corresponding to an edge of $G$. Suppose the crossing set of $C$
contains $k$ such edges. Let $A$ denote the corresponding edges in $G$. Then
$A$ is the crossing set of a cocircuit in $G$ of size $k$. From each such
cocircuit we can construct $l^{k}$ cocircuits of $G_{l}$ by choosing one edge
from each path corresponding to an edge in $A$. The claim then follows.

If we compute $N(G_{1}),\ldots,N(G_{m})$ then we may retrieve
$N_{1}(G),\ldots,N_{m}(G)$ by using Gaussian elimination because the matrix of
coefficients of the linear equations is an invertible Vandermonde matrix. The
fact that the Gaussian elimination may be carried out in polynomial time
follows from [22]. ∎

######  Lemma 4.6.

$\\#$Cocircuits $\propto$ $\chi_{convex}(-;2)$

###### Proof.

The lemma is easily proved using the following observation. When two colors
are available, there are two convex colorings of a connected graph using just
one color and the number of convex colorings using both colors is equal to
twice the number of cocircuits. ∎

The preceding lemmas imply our main result, Theorem 3.5, that
$\chi_{convex}(-;2)$ is $\\#$P-hard.

##  5 Detailed case study: Discrete spectra

In this section we dicuss cases where we were not able to find a suitable
version of Linial’s Trick, but where we could determine the complexity of the
evaluations for non-negative integers.

###  5.1 Proper edge colorings

Recall that $\chi_{edge}(G;k)$ counts the number of proper edge colorings of a
graph $G$ with $k$ colors. It is a polynomial in $k$ because

$\chi_{edge}(G;k)=\chi(L(G);k),$

where $L(G)$ is the line graph of $G$ and $\chi(G;k)$ is the chromatic
polynomial. We have $\chi_{edge}(G;0)=0$ and

$\chi_{edge}(G;1)=\begin{cases}1&\mbox{if }G\mbox{ consists of isolated edges
and vertices}\\\ 0&\mbox{otherwise}\end{cases}$

Although $\chi_{e}dge(G;k)=\chi(L(G);k)$, where $L(G)$ is the line graph of
$G$, not every graph $G$ is the line graph of some graph $G^{\prime}$.

The class of all finite line graphs, $\mathcal{LG}$, has been completely
characterized, [8, 11].

######  Theorem 5.1 (Beineke, 1970, [8]).

There are nine graphs $F_{i}:1\leq i\leq 9$, each with at most $6$ vertices,
such that $G\in\mathcal{LG}$ if and only if no $F_{i}$ is an induced subgraph
of $G$.

The complexity spectrum of the chromatic polynomial restricted to the class
$\mathcal{LG}$ has, to the best of our knowledge, not been studied.

Surprisingly, the complexity of counting proper edge colorings was proven
$\\#{\mathbf{P}}$-hard only recently, [16]:

######  Theorem 5.2 (J. Y. Cai, H. Guo, T. Williams, 2014).

For $k\in{\mathbb{N}}$ we have:

  1. (i)

$\chi_{edge}(G;k)$ is $\\#{\mathbf{P}}$-hard over planar $r$-regular graphs
for all $k\geq r\geq 3$.

  2. (ii)

$\chi_{edge}$ is trivially tractable when $k\geq r\geq 3$ does not hold.

The proof given in [16] reduces $\chi_{edge}(G;k)$ to computation of the
diagonal of the Tutte polynomial $T(G;X,X)$ using several intermediate steps
via holants999 For background on holants, cf. [53, 19].

######  Problem 5.3.

Find an elementary (holant-free) proof of Theorem 5.2.

Theorem 5.2 gives us the discrete complexity spectrum for $k\in{\mathbb{N}}$.

We were unable to adapt Linial’s Trick to proper edge colorings. Therefore we
do not know how to determine the complexity of $\chi_{edge}(G;X)$ for $X=a$
and $a\in{\mathbb{C}}-{\mathbb{N}}$ or even $a\in{\mathbb{Q}}-{\mathbb{N}}$.

######  Problem 5.4.

Determine the full complexity spectrum of $\chi_{edge}(G;X)$ for $X=a$ and
$a\in{\mathbb{Q}}$ or $a\in{\mathbb{C}}$.

###  5.2 $mcc_{t}$-colorings

Let $t\in{\mathbb{N}}$. Recall that a coloring $f:V(G)\rightarrow[k]$ is an
$mcc_{t}$ -coloring with $k$ colors, if the connected components of each color
class have at most $t$ vertices.

We easily verify:

######  Proposition 5.5.

  1. (i)

For fixed $t\in{\mathbb{N}}^{+}$ being an $mcc_{t}$ -coloring with $k$ colors
is a $\mathbf{CP}$-property, hence $\chi_{mcc_{t}}(G;k)$ is a polynomial in
$k$ (but not in $t$).

  2. (ii)

$\chi_{mcc_{t}}(G;k)$ is multiplicative over disjoint unions.

  3. (iii)

For $t=1$ we have $\chi_{mcc_{1}}(G;k)=\chi(G;k)$, i.e., it is the chromatic
polynomial.

  4. (iv)

For $k=1$ a graph $G$ is $mcc_{t}$ -colorable iff $G$ is a disjoint union of
connected graphs $H$ with at most $t$ vertices.

We next establish a complexity result.

######  Theorem 5.6.

Computing $\chi_{mcc_{t}}(G;2)$ is $\\#{\mathbf{P}}$-complete for $t\geq 2$.

(a) Clause gadget

(b) Bridge

Figure 2: Clause gadget LABEL:sub@fig:clause-gadget for a clause
$c=\mathrm{NAE}_{4}(x_{1},x_{2},x_{3},x_{4})$ and a bridge
LABEL:sub@fig:bridge-gadet connecting two vertices labeled by the same
variable $x_{1}$ in two different clauses
$c_{1}=\mathrm{NAE}_{4}(x_{1},y_{2},y_{3},y_{4})$ and
$c_{2}=\mathrm{NAE}_{4}(x_{1},z_{2},z_{3},z_{4})$.

To prove Theorem 5.6 we use a result due to Creignou and Hermann [17]. Let
$\mathrm{NAE}_{k}$ be a Boolean relation of arity $k$ of all tuples having at
least one $0$ and at least one $1$, i.e.
$\mathrm{NAE}_{k}=\\{0,1\\}^{k}\smallsetminus\\{0\cdots 0,1\cdots 1\\}$,
commonly called the not-all-equal relation. Let
$\mathrm{NAE}_{k}(x_{1},\dots,x_{k})$ be a constraint which is satisfied only
by all tuples from the relation $\mathrm{NAE}_{k}$. A $\mathrm{NAE}_{k}$
formula $\varphi=c_{1}\land\cdots\land c_{n}$ is satisfied if each clause
$c_{i}$ is not-all-equal satisfied. Given a CNF formula $\varphi$, the
counting problem $\\#\mathrm{NAE}_{k}\mathrm{SAT}$ asks for the number of not-
all-equal satisfying assignments of $\varphi$.

######  Theorem 5.7 ([17]).

$\\#\mathrm{NAE}_{k}\mathrm{SAT}$ is $\\#{\mathbf{P}}$-complete for each
$k\geq 3$.

###### Proof of Theorem 5.6.

The membership in $\\#{\mathbf{P}}$ is clear, therefore we focus on the proof
of $\\#{\mathbf{P}}$-hardness. We perform a parsimonious reduction from
$\\#\mathrm{NAE}_{t+1}\mathrm{SAT}$.

Given a $\mathrm{NAE}_{t+1}$ formula $\varphi$, we associate with it the graph
$G_{\varphi}$ in the following way. For each clause
$c=\mathrm{NAE}_{t+1}(x_{1},\ldots,x_{t+1})$ construct the clause gadget (as
in Figure 2a for $t=3$), consisting of a complete graph $K_{2t}$. Label $t+1$
vertices of $K_{2t}$ by the variables $x_{1}$, …, $x_{t+1}$ and the remaining
$t-1$ vertices by $c^{1}$, …, $c^{t-1}$, where $c$ is the identifier of the
clause.

Connect different copies of the same variable in two clause gadgets by a
bridge with a new vertex $b$. There is a new bridge vertex $b$ for each pair
of variable vertices labeled by the same variable $x$ in different clause
gadgets. Figure 2b illustrates (for $t=3$) how two copies of the variable
$x_{1}$ in clauses $c_{1}=\mathrm{NAE}_{t+1}(x_{1},y_{2},\ldots,y_{t+1})$ and
$c_{2}=\mathrm{NAE}_{t+1}(x_{1},z_{2},\ldots,z_{t+1})$ are connected through a
bridge with a new node $b$.

We show that each $mcc_{t}$-coloring of the graph $G_{\varphi}$ encodes a
$\mathrm{NAE}_{t+1}$-satisfiability of the formula $\varphi$. A valid
$mcc_{t}$ $2$-coloring of each clause gadget forces $t$ variables to be
colored by the color $0$ and the $t$ others by the color $1$. Restricted to
the variable nodes $x_{1}$, …, $x_{t+1}$ of the clause gadget, this represents
a correct assignment of the constraint
$\mathrm{NAE}_{t+1}(x_{1},\ldots,x_{t+1})$. No other $2$-coloring of the
clause gadget is a valid $mcc_{t}$ coloring.

When two occurrences of the same variable $x$ are connected through a bridge
with a vertex $b$, this bridge vertex $b$ must be colored by a different color
than the vertices labeled by $x$. Indeed, in a valid $mcc_{t}$ coloring, the
vertex $x$ in the clause gadget is connected to another $t-1$ vertices colored
by the same color. This induces a different color for the vertex $b$,
otherwise there would be a connected component containing $t+1$ vertices and
colored by the same color. This also forces the two copies of the variable
$x$, connected by a bridge, to be colored by the same color.

Hence, the satisfying assignments of a $\mathrm{NAE}_{t+1}\mathrm{SAT}$
formula $\varphi$ are in one-to-one correspondence to the $mcc_{t}$
$2$-colorings of $G_{\varphi}$, which constitutes a parsimonious reduction
from $\\#\mathrm{NAE}_{t+1}\mathrm{SAT}$. ∎

Next we determine the complexity of $\chi_{mcc_{t}}(G;k)$ for
$k,t\in{\mathbb{N}}$.

######  Theorem 5.8.

For any integers $t$ and $k$ that are both at least two, $\chi_{mcc_{t}}(G;k)$
is $\\#$P-complete.

###### Proof.

Membership in $\\#{\mathbf{P}}$ is clear. We shall show that if $t$ and $k$
are integers and both at least two, then $\chi_{mcc_{t}}(G;k)$ is polynomial
time reducible to $\chi_{mcc_{t}}(G;k+1)$. Combining this with Theorem 5.6
gives the result.

Given a graph $G$, form $G^{\prime}$ from $G$ by adding a clique on $t(k+1)$
new vertices and joining one of the new vertices to every vertex of $G$. In
any valid coloring of $G^{\prime}$ with $k+1$ colors, each color class must
contain precisely $t$ of the new vertices and these vertices can be colored in
$\binom{(k+1)t}{t,t,\ldots,t}$ ways, where $\binom{(k+1)t}{t,t,\ldots,t}$ is
the multinomial coefficient counting the number of ways of choosing an ordered
collection of $k+1$ subsets each of size $t$ from a set of size $(k+1)t$. Once
the new vertices have been colored there are $k$ colors available to color the
vertices of $G$. Thus

$\chi_{mcc_{t}}(G^{\prime};k+1)=\binom{(k+1)t}{t,t,\ldots,t}\chi_{mcc_{t}}(G;k).$

The result follows. ∎

######  Remark 4.

The statement

$\chi_{mcc_{t}}(G^{\prime};k+1)=\binom{(k+1)t}{t,t,\ldots,t}\chi_{mcc_{t}}(G;k).$

appears at first sight to be an instance of Linial’s Trick, but there is a
subtle difference. In the proof above the choice of $G^{\prime}=f(G,t,k)$ both
depends on $t$ and $k$.

In applying Linial’s Trick we require that the graph $G^{\prime}=g(G)$ does
not depend on $k$ in order to get a polynomial identity of the form

$\chi_{mcc_{t}}(g^{n}(G);k+n)=f(k,n,t)\cdot\chi_{mcc_{t}}(G;k).$

Currently we do not know whether there is a version of Linial’s Trick which
can be used for $\chi_{mcc_{t}}(G;X)$.

Using the fact that $\chi_{mcc_{1}}(G;X)$ is the chromatic polynomial and the
previous discussion (Proposition 5.5, and Theorems 5.6 and 5.8) we get

######  Corollary 5.

Evaluating $\chi_{mcc_{t}}(G;X)$ is in ${\mathbf{P}}$ for $t=1$ and $k=0,1,2$,
and for $t\geq 2$ and $k=1$. For all other values of $t,k\in{\mathbb{N}}$
evaluation is $\\#{\mathbf{P}}$-complete.

######  Problem 5.9.

What is the complexity spectrum for $\chi_{mcc_{t}}(G;a)$ for $t\geq 2$ and
$a\in{\mathbf{F}}-{\mathbb{N}}$?

In Theorem 3.16 we have determined completely the complexity spectrum for
$\chi_{DU(K_{\alpha})}(G;X)$. This was meant to be a warm-up exercise for
determining the complexity spectrum for $\chi_{mcc_{t}}(G;X)$, as each
$DU(K_{\alpha})$-coloring is also an $mcc_{\alpha}$-coloring. However,
determining the difficulty of evaluating $\chi_{mcc_{t}}(G;X)$ seems to be
much more demanding.

###  5.3 $H$-free-colorings

A function $f:V(G)\to[k]$ is an $H$-free coloring if no color class induces a
graph isomorphic to $H$. Clearly this is a $\mathbf{CP}$-property, hence
$\chi_{H-free}(G;k)$ is a polynomial in $k$. The discrete complexity spectrum
is rather well understood:

######  Theorem 5.10.

  1. (i)

([1]) $\chi_{H-free}(G;k)$ is $\\#{\mathbf{P}}$-hard for every $k\geq 3$ and
$H$ with at least $2$ vertices.

  2. (ii)

([2]) $\chi_{H-free}(G;2)$ is ${\mathbf{NP}}$-hard for every $H$ with at most
$2$ vertices.

It is easy to see that for $X=0,1$ we have the following evaluations:

$\chi_{H-free}(G;0)=0$

and

$\chi_{H-free}(G;1)=\begin{cases}1&\mbox{if }G\mbox{ is }H-\mbox{free}\\\
0&\mbox{ otherwise }.\end{cases}$

######  Problem 5.11.

What is the complexity of evaluation of $\chi_{H-free}(G;a)$ for
$a\in{\mathbf{F}}-{\mathbb{N}}$?

$H$-free coloring is another case where Linial’s Trick does not seem to work.

##  6 More graph polynomials

In this section we discuss some graph polynomials for which we have only
partial knowledge, if any, about the complexity spectrum. The graph
polynomials $\chi_{\Phi}(G;k)$ we discuss arise from $\mathbf{CP}$-properties
$\Phi$ defined in Section 6.1. Three of them, (i-iii), belong to the framework
of $\mathcal{P}_{1}-\mathcal{P}_{2}$-colorings from Subsection 2.2, listed in
Table 3, and the remaining two, (iv,v), are mentioned here because they have a
rich literature.

In each case we do not know — but suspect — that evaluation of
$\chi_{\Phi}(G;X)$ is $\\#{\mathbf{P}}$-hard for $X=a$ for at least one
$a\in{\mathbf{F}}$.

######  Problem 6.1.

Determine the full complexity spectrum of $\chi_{\Phi}(G;X)$ for each of the
graph polynomials in Section 6.1.

Instead of counting colorings one can look at the corresponding decision
problem which asks whether $\chi_{\Phi}(G;k)>0$. Clearly, the counting problem
is at least as hard as this decision problem. For each of the graph properties
$\Phi$ above we do know that computing the polynomial $\chi_{\Phi}(G;X)$ is
${\mathbf{NP}}$-hard. Furthermore, in two cases we discuss dichotomy theorems
showing that an evaluation of $\chi_{\Phi}(G;X)$ is either in ${\mathbf{P}}$
or ${\mathbf{NP}}$-hard.

###  6.1 Graph polynomials with incomplete complexity spectrum

We consider the following colorings:

  1. (i)

Let $t\in\mathbb{N}$. A function $c:V(G)\rightarrow[k]$ is a $t$-improper
coloring if every color induces a graph of maximal degree $t$. $t$-improper
colorings were studied in [15]. They originate in certain network problems.

  2. (ii)

A function $c:V(G)\rightarrow[k]$ is an acyclic coloring if it is proper and
there is no two colored cycle in $G$. Acyclic colorings were introduced in
[29] and further studied in [5].

  3. (iii)

A function $f:V(G)\rightarrow[k]$ is a co-coloring if every color class
induces a graph which is either a clique or an independent set. Co-colorings
were first studied in [31].

  4. (iv)

A function $f:E(G)\rightarrow[k]$ is a rainbow-path coloring (rainbow coloring
for short) if every two vertices are connected by a path in which every two
edges are colored differently. Rainbow colorings were first introduced in
[18].

  5. (v)

A function $f:V(G)\to[k]$ is an injective coloring if it is injective on the
open neighborhood of every vertex. $f$ does not have to be a proper coloring.
In other words, if there is a path of length $2$ between $v$ and $u$ then $u$
and $v$ must have different colors.

Let $\Phi_{t-imp}$, $\Phi_{acyc}$, $\Phi_{co-co}$, $\Phi_{rainbow}$, and
$\Phi_{inject}$ denote respectively the coloring properties of $t$-improper
colorings for fixed $t\in\mathbb{N}$, acyclic colorings, co-colorings, rainbow
colorings, and injective colorings. Clearly, each of these coloring properties
$\Phi$ is a $\mathbf{CP}$-property, and hence the number of colorings in each
$\Phi$ is a polynomial in $k$. We denote by $\chi_{t-imp}(G;k)$,
$\chi_{acyc}(G;k)$, $\chi_{co-co}(G;k)$, $\chi_{rainbow}(G;k)$, and
$\chi_{inject}(G;k)$ the graph polynomials $\chi_{\Phi}(G;k)$ counting
colorings with at most $k$ colors of a graph $G$ in the corresponding $\Phi$.

For acyclic colorings, co-colorings, rainbow colorings and injective
colorings, the complexity spectrum is completely unknown. For $t$-improper
colorings, partial results are known. For $t=0$, the $t$-improper colorings
are exactly the proper colorings, hence $\chi_{0-imp}(G;k)=\chi(G;k)$ and the
complexity spectrum is completely understood. For $t=1$ and $k\in{\mathbb{N}}$
we have $\chi_{1-imp}(G;k)=\chi_{mcc_{2}}(G;k)$ and the complexity spectrum is
completely understood. For $t=2$ every color class consists of a disjoint
union of paths and cycles. This is the first case where the complexity
spectrum of $\chi_{2-imp}(G;k)$ is not known.

###  6.2 ${\mathbf{NP}}$-hardness

From the literature, we have that each of the graph polynomials defined in
Section 6.1 is ${\mathbf{NP}}$-hard:

######  Theorem 6.2.

  1. (i)

Let $t\in\mathbb{N}$. Let $\Phi$ be one of $\Phi_{t-imp}$ $\Phi_{co-co}$,
$\Phi_{rainbow}$, and $\Phi_{inject}$. Computing the minimal
$k\in{\mathbb{N}}$ such that $\chi_{\Phi}(G;k)>0$ is ${\mathbf{NP}}$-hard.

  2. (ii)

It is NP-hard to decide for a given $G$ and $k$ if the acyclic chromatic
number of $G$ is at most $k$.

###### Proof.

The case of $t$-improper colorings in Theorem 6.2(i) follows directly from
[15]. The case of co-colorings is proven in [24]. The case of rainbow
colorings is proven in [14]. The case of injective colorings follows directly
from [33]. Theorem 6.2(ii) is proven in [39]. ∎

For $t$-improper colorings we are able to give a dichotomy theorem for graphs
with multiple edges:

######  Proposition 6.3.

  1. (i)

For every $a\in{\mathbf{F}}-\\{0,1\\}$ the problem of evaluating
$\chi_{t-imp}(G;a)$, where the input runs over the class of graphs with
multiple edges allowed, is ${\mathbf{NP}}$-hard.

  2. (ii)

The evaluations $\chi_{t-imp}(G;0)$ and $\chi_{t-imp}(G;1)$ are in
${\mathbf{P}}$.

###### Proof.

Let $G\bowtie_{t}K_{1}$ be the graph obtained from $G$ by adding a new vertex
$v$ and putting $t+1$ edges between $v$ and any vertex of $G$. Clearly, $v$
cannot be colored the same color as any other vertex of $G$. Therefore, we can
use Linial’s Trick. ∎

For acyclic colorings, we have a partial dichotomy. The evaluations of
$\chi_{acyc}(G;X)$ with $X=0$ and $X=1$ are trivial by definition, because
every proper coloring with less than two colors is acyclic.

######  Proposition 6.4.

For every $a\notin\mathbb{N}$, it is NP-hard to compute $\chi_{acyc}(G;a)$.

###### Proof.

We use a version of Linial’s Trick for the chromatic polynomial. Consider
$G\bowtie K_{1}$. Every acyclic coloring $f$ of $G\bowtie K_{1}$ with color
set $[k]$ must color the vertex $K_{1}$ with a unique color. The coloring
$f\mid_{G}$ induced by $f$ on $G$ is clearly proper and does not contain any
two-colored cycles, since $f$ is acyclic. On the other hand, every acyclic
coloring $g$ of $G$ with color set $[k-1]$ can be transformed to an acyclic
coloring $f$ of $G\bowtie K_{1}$ with color set $[k]$ by coloring $K_{1}$ with
any of the $k$ colors, and then setting

$f(v)=\begin{cases}g(v)&g(v)<f(K_{1})\\\ g(v)+1&g(v)\geq f(K_{1})\end{cases}$

for any $v\in V(G)$. Hence we get

$\chi_{acyc}(G\bowtie K_{1};x_{0})=\chi_{acyc}(G;x_{0}-1)\cdot x_{0}\,.$

Using Theorem 6.2(ii) we complete the proof. ∎

A solution of the following problem would complete the dichotomy:

######  Problem 6.5.

What is the complexity of the evaluation $\chi_{acyc}(G;a)$ for
$a\in{\mathbb{N}}-\\{0,1\\}$?

##  7 Conclusions and open problems

In the light of the discovery of many univariate graph polynomials in [38],
and the fact that infinitely many of them are incomparable in expressive
power, Theorem 2.3, we initiated the systematic study of these graph
polynomials. Inspired by N. Linial’s work in [42] we have concentrated in this
paper on the complexity of evaluating these graph polynomials. We have
introduced the full and the discrete complexity spectrum of univariate graph
polynomials. In this paper we concentrated our attention on graph polynomials
arising from graph colorings previously studied in the literature.

Throughout the paper we have listed101010 These are Problems 1.6, 2.4, 5.3,
5.4, 3.10, 5.9, 5.11, 6.1 and 6.5.  open problems we encountered in our
explorations. They mostly ask for the complete determination of the full
complexity spectrum for specific graph polynomials. Among the more interesting
challenges we have the following:

######  Problem 7.1.

Determine the full complexity spectrum of

  1. (i)

the edge chromatic polynomial $\chi_{edge}(G;X)$;

  2. (ii)

the polynomial $\chi_{mcc_{t}}(G;X)$ for $t\geq 2$;

  3. (iii)

the polynomials $\chi_{H-free}(G;X)$ for $t\geq 2$;

  4. (iv)

the generalized chromatic polynomials derived from $t$-improper colorings,
acyclic colorings, co-colorings, rainbow-path colorings and injective
colorings of Section 6.

We have not found a single graph polynomial which does not have a complexity
spectrum satisfying the Difficult Point Dichotomy. Our results so far suggest
that there might be meta-theorem to be formulated, and finally also to be
proven, which says that for a large class of graph polynomials Difficult Point
Dichotomy holds. The large class in question should be defined by some
definability criterion. Examples of such criteria could come from descriptive
complexity theory.

Here are some candidates for logically defined classes111111 For a discussion
of logically defined classes of graph polynomials,
see [44, 46, 38, 40].  of univariate graph polynomials

  1. (i)

All ${\mathrm{SOL}}$-definable graph polynomials.

  2. (ii)

All ${\mathrm{MSOL}}$-definable graph polynomials.

  3. (iii)

All $\mathcal{P}$-chromatic polynomials where $\mathcal{P}$ is in
${\mathbf{NP}}$, or equivalently, where $\mathcal{P}$ is definable in
$\exists{\mathrm{SOL}}$, the existential fragment of ${\mathrm{SOL}}$.

Previous experience suggests that it is too early to formulate a solid
conjecture.

######  Problem 7.2.

Formulate and prove a meta-theorem for the Difficult Point Dichotomy.

We hope the search for a meta-theorem will spawn further research and will
lead to new insights both in graph theory and in descriptive complexity
theory.

### Acknowledgements

We would like to thank two anonymous referees of an earlier version of this
paper for their accurate reading and spotting gaps and imprecisions, and for
their extremely valuable comments. We would also like to thank the editors of
this special issue, J. Ellis-Monaghan, J. Kung and I. Moffatt for their
patience and support.

## References

## References

  * ABCM [98] D. Achlioptas, J. I. Brown, D. G. Corneil, and M. SO. Molloy.  The existence of uniquely- g colourable graphs.  Discrete Mathematics, 179(1):1–11, 1998.
  * Ach [97] D. Achlioptas.  The complexity of G-free colourability.  Discrete Mathematics, 165:21–30, 1997.
  * ADOV [03] N. Alon, G. Ding, B. Oporowski, and D. Vertigan.  Partitioning into graphs with only small components.  Journal of Combinatorial Theory, Series B, 87(2):231–243, 2003\.
  * [4] I. Averbouch and J.A. Makowsky.  The complexity of multivariate matching polynomials.  Preprint, January 2007.
  * AMR [91] N. Alon, C. McDiarmid, and B. Reed.  Acyclic coloring of graphs.  Random Structures and Algorithms, 2.3:277–288, 1991.
  * AS [87] K. Ambos-Spies.  Polynomial time degrees of np-sets.  In E. Börger, editor, Trends in Theoretical Computer Science, pages 95–142. Computer Science Press, 1987.
  * BDM [10] M. Bläser, H. Dell, and J. A. Makowsky.  Complexity of the Bollobás-Riordan polynomial. exceptional points and uniform reductions.  Theory of Computing Systems, 46(4):690–706, 2010.
  * Bei [70] L. W. Beineke.  Characterizations of derived graphs.  Journal of Combinatorial Theory, 9(2):129–135, 1970.
  * BG [05] A. Bulatov and M. Grohe.  The complexity of partition functions.  Theoretical Computer Science, 348:148–186, 2005.
  * Bir [12] G.D. Birkhoff.  A determinant formula for the number of ways of coloring a map.  Annals of Mathematics, 14:42–46, 1912.
  * BLS [99] A. Brandstädt, V.B. Le, and J. Spinrad.  Graph Classes: A survey.  SIAM Monographs on Discrete Mathematics and Applications. SIAM, 1999.
  * Bro [96] J. I. Brown.  The complexity of generalized graph colorings.  Discrete Applied Mathematics, 69(3):257 – 270, 1996.
  * CCL [13] Jin-Yi Cai, Xi Chen, and Pinyan Lu.  Graph homomorphisms with complex values: A dichotomy theorem.  SIAM Journal of Computation, 42(3):924–1029, 2013.
  * CFMY [11] S. Chakraborty, E. Fischer, A. Matsliah, and R. Yuster.  Hardness and algorithms for rainbow connection.  Journal of Combinatorial Optimization, 21(3):330–347, 2011.
  * CGJ [97] L. Cowen, W. Goddard, and C. E. Jesurum.  Defective coloring revisited.  Journal of Graph Theory, 24(3):205–219, 1997.
  * CGW [14] J. Cai, H. Guo, and T. Williams.  The complexity of counting edge colorings and a dichotomy for some higher domain holant problems.  In Foundations of Computer Science (FOCS), 2014 IEEE 55th Annual Symposium on, pages 601–610. IEEE, 2014.
  * CH [96] N. Creignou and M. Hermann.  Complexity of generalized satisfiability counting problems.  Information and Computation, 125:1–12, 1996.
  * CJMZ [08] G. Chartrand, G.L. Johns, K.A. McKeon, and P. Zhang.  Rainbow connection in graphs.  Mathematica Bohemica, 133(1):85–98, 2008.
  * CLX [11] J. Cai, P. Lu, and M. Xia.  Computational complexity of holant problems.  SIAM Journal on Computing, 40(4):1101–1132, 2011.
  * DBG [17] E. Drgas-Burchardt and K. Gibek.  Harmonious colourings of graphs.  Discrete Applied Mathematics, 217:175–184, 2017.
  * DG [00] M. Dyer and C. Greenhill.  The complexity of counting graph homomorphisms.  Random Structures and Algorithms, 17.3-4:260 – 289, 2000.
  * Edm [67] J. Edmonds.  Systems of distinct representatives and linear algebra.  Journal of Research of the National Bureau of Standards Section B, 71B:241–245, 1967.
  * Edw [97] K. Edwards.  The harmonious chromatic number and the achromatic number.  In R. A. Bailey, editor, Survey in Combinatorics, volume 241 of London Math. Soc. Lecture Note Ser., pages 13–47. Cambridge Univ. Press, 1997.
  * EGK [91] P. Erdös, J. Gimbel, and D. Kratsch.  Some extremal results in cochromatic and dichromatic theory.  Journal of Graph Theory, 15(6):579–585, 1991.
  * EM [95] K. Edwards and C. McDiarmid.  The complexity of harmonious colouring for trees.  Discrete Applied Mathematics, 57(2-3):133–144, 1995.
  * Far [04] A. Farrugia.  Vertex-partitioning into fixed additive induced-hereditary properties is NP-hard.  Electronic Journal of Combinatorics, 11(1), 2004.
  * GJ [79] M.G. Garey and D.S. Johnson.  Computers and Intractability.  Mathematical Series. W.H. Freeman and Company, 1979.
  * GN [08] A. J. Goodall and S. D. Noble.  Counting cocircuits and convex two-colourings is# p-complete.  arXiv preprint arXiv:0810.2042, 2008.
  * Gru [73] B. Grunbaum.  Acyclic colorings of planar graphs.  Israel Journal Mathematics, 14:390–412, 1973.
  * HIMRS [98] H. B. Hunt III, M. V. Marathe, V. Radhakrishnan, and R. E. Stearns.  The complexity of planar counting problems.  SIAM Journal on Computing, 27(4):1142–1167, 1998.
  * HJL [77] L.; Straight H. J. Lesniak.  The cochromatic number of a graph.  Ars Combinatoria, 3:39–46, 1977.
  * HK [83] J.E. Hopcroft and M.S. Krishnamoorthy.  On the harmonious coloring of graphs.  SIAM Journal on Algebraic Discrete Methods, 4:306–311, 1983.
  * HKSS [02] G. Hahn, J. Kratochvil, J. Siran, and D. Sotteau.  On the injective chromatic number of graphs.  Discrete Mathematics, 256.1-2:179–192, 2002.
  * KH [83] D.G. Kirkpatrick and P. Hell.  On the complexity of general graph factor problems.  SIAM Journal on Computing, 12:601–609, 1983.
  * KM [14] T. Kotek and J.A. Makowsky.  Connection matrices and the definability of graph parameters.  Logical Methods in Computer Science, 10(4), 2014.
  * KMR [17] T. Kotek, J.A. Makowsky, and E.V. Ravve.  On sequences of graph polynomials arising from graph invariants.  European Journal of Combinatorics, xxx:xx–yy, submitted 2017.
  * KMZ [08] T. Kotek, J.A. Makowsky, and B. Zilber.  On counting generalized colorings.  In Computer Science Logic, CSL’08, volume 5213 of Lecture Notes in Computer Science, pages 339–353, 2008.
  * KMZ [11] T. Kotek, J.A. Makowsky, and B. Zilber.  On counting generalized colorings.  In M. Grohe and J.A. Makowsky, editors, Model Theoretic Methods in Finite Combinatorics, volume 558 of Contemporary Mathematics, pages 207–242. American Mathematical Society, 2011.
  * Kos [78] A. V. Kostochka.  Upper bounds of chromatic function.  PhD thesis, Ph. D. Thesis, Novosibirsk, 1978 (in Russian), 1978.
  * Kot [12] T. Kotek.  Definability of combinatorial functions.  PhD thesis, Technion - Israel Institute of Technology, Haifa, Israel, March 2012.
  * Lad [75] R.E. Ladner.  On the structure of polynomial time reducibility.  Journal of ACM, 22(1):155–171, 1975.
  * Lin [86] M. Linial.  Hard enumeration problems in geometry and combinatorics.  SIAM Journal of Algebraic and Discrete Methods, 7:331–335, 1986\.
  * LMST [07] N. Linial, J. Matousek, O. Sheffet, and G. Tardos.  Graph coloring with no large monochromatic components.  Electronic Notes in Discrete Mathematics, 29:115–122, 2007.
  * [44] J.A. Makowsky.  From a zoo to a zoology: Towards a general theory of graph polynomials.  Theory of Computing Systems, 43:542–562, 2008.
  * [45] J.A. Makowsky.  Problem posed at the problem session at “Building Bridges: A conference on mathematics and computer science in honour of Laci Lovász”, 2008.
  * MKR [13] J.A. Makowsky, T. Kotek, and E.V. Ravve.  A computational framework for the study of partition functions and graph polynomials.  In Proceedings of the 12th Asian Logic Conference ’11, pages 210–230. World Scientific, 2013.
  * MRB [14] J.A. Makowsky, E.V. Ravve, and N.K. Blanchard.  On the location of roots of graph polynomials.  European Journal of Combinatorics, 41:1–19, 2014.
  * MS [07] S. Moran and S. Snir.  Efficient approximation of convex recolorings.  Journal of Computer and System Sciences, 73(7):1078–1089, 2007\.
  * MZ [06] J.A. Makowsky and B. Zilber.  Polynomial invariants of graphs and totally categorical theories.  MODNET Preprint No. 21,
http://www.logique.jussieu.fr/
modnet/Publications/Preprint%20 server, 2006\.

  * Pap [94] C. Papadimitriou.  Computational Complexity.  Addison Wesley, 1994.
  * PB [83] J.S. Provan and M.O. Ball.  The complexity of counting cuts and of computing the probability that a graph is connected.  SIAM Journal of Computing, 12(4):777–788, 1983.
  * Val [79] L.G. Valiant.  The complexity of enumeration and reliability problems.  SIAM Journal on Computing, 8(3):410–421, 1979.
  * Val [08] L. G. Valiant.  Holographic algorithms.  SIAM Journal on Computing, 37(5):1565–1594, 2008.