Short certicates for chromatic equivalence

Zoe Elizabeth Bukovac, Graham Farr, Kerri Jo-Anne Morgan

Research output: Contribution to journalArticleResearchpeer-review


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 there are pairs of chromatically equivalent graphs on n vertices with certificate of chromatic equivalence of length Ω(n2= 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 7.
Original languageEnglish
Pages (from-to)227-269
Number of pages43
JournalJournal of Graph Algorithms and Applications
Issue number2
Publication statusPublished - 2019

Cite this