Bivariate chromatic polynomials in computer algebra. (July 2019) - Gerling, Melanie
Abstract: The computation of the chromatic polynomial of a graph, which was introduced byBirkhoff (1912), is an NP-complete problem. Consequently, this is also valid for the bivariate generalization of the chromatic polynomial byDohmen et al. (2003) . A recursion formula, which was presented byAverbouch et al. (2008), has exponential complexity. Hence, the aim of the current article is to find efficient algorithms or formulas for the calculation of the bivariate chromatic polynomial for special types of graphs. The following results will be presented: We found efficient formulas for complete graphs, from which the edges of stars with pairwise different vertices are deleted, for complete partite graphs and for special split graphs. Furthermore, in a section about separators, we show that the special case of separating complete subgraphs, which is very simple in the univariate case, requires rather complex methods in the bivariate case. Finally, we establish a connection between the bivariate chromatic polynomial and the matching polynomial for complete graphs from which the edges of stars with pairwise different vertices are removed, as well as for bi-cliques. Some algorithms are implemented in Mathematica, and examples are presented.