Bivariate chromatic polynomials in computer algebra. (July 2019)

• Record Type: Journal Article
• Authors: Gerling, Melanie
• Is Part Of: Journal of symbolic computation. Volume 93(2019)
• Page Start: 183
• Page End: 199
• Publication Date: 2019-07
• Subjects: Graph theory -- Algorithms; Mathematics -- Data processing -- Periodicals; Numerical analysis -- Data processing -- Periodicals; Automatic programming (Computer science) -- Periodicals; Mathématiques -- Informatique -- Périodiques; Analyse numérique -- Informatique -- Périodiques; Programmation automatique -- Périodiques; Automatic programming (Computer science); Mathematics -- Data processing; Numerical analysis -- Data processing; Periodicals; Electronic journals; 510.285
• DOI: 10.1016/j.jsc.2018.06.006
• Languages: English
• ISSNs: 0747-7171

Abstract

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.