Short certificates for chromatic equivalence

Abstract

The chromatic polynomial gives the number of proper colourings of a graph in terms of the number of available colours. In general, calculating chromatic polynomials is #P-hard. Two graphs are chromatically equivalent if they have the same chromatic polynomial. At present, determining if two graphs are chromatically equivalent involves computation and comparison of their chromatic polynomials, or similar computational effort. In this paper we investigate a new approach, certificates of chromatic equivalence, first proposed by Morgan and Farr. These give proofs of chromatic equivalence, without directly computing the polynomials. The lengths of these proofs may provide insight into the computational complexity of chromatic equivalence and related problems including chromatic factorisation and chromatic uniqueness. For example, if the lengths of shortest certificates of chromatic equivalence are bounded above by a polynomial in the size of the graphs, then chromatic equivalence belongs to NP. After establishing some links of this type between certificate length and computational complexity, we give some theoretical and computational results on certificate length. We prove that, if the number of different chromatic polynomials falls well short of the number of different graphs, then for all sufficiently large $n$ there are pairs of chromatically equivalent graphs on $n$ vertices with certificate of chromatic equivalence of length $\Omega(n^2/\log n)$. We give a linear upper bound on shortest certificate length for trees. We designed and implemented a program for finding short certificates of equivalence using a minimal set of certificate steps. This program was used to find the shortest certificates of equivalence for all pairs of chromatically equivalent graphs of order $n\leq 7$.