Home | Issues | About JGAA | Instructions for Authors |
DOI: 10.7155/jgaa.00490
Short certificates for chromatic equivalence
Zoe Bukovac,
Graham Farr, and
Kerri Morgan
Vol. 23, no. 2, pp. 227-269, 2019. Regular paper.
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$.
|
Submitted: November 2016.
Reviewed: January 2019.
Revised: January 2019.
Accepted: February 2019.
Final: March 2019.
Published: April 2019.
Communicated by
Michael Kaufmann
|
Journal Supporters
|