Chromatic Polynomials of Complements of Bipartite Graphs |
| |
Authors: | Adam Bohn |
| |
Affiliation: | 1. School of Mathematical Sciences Queen Mary, University of London, Mile End Road, London, E1 4NS, UK
|
| |
Abstract: | We define a biclique to be the complement of a bipartite graph, consisting of two cliques joined by a number of edges. In this paper we study algebraic aspects of the chromatic polynomials of these graphs. We derive a formula for the chromatic polynomial of an arbitrary biclique, and use this to give certain conditions under which two of the graphs have chromatic polynomials with the same splitting field. Finally, we use a subfamily of bicliques to prove the cubic case of the α + n conjecture, by showing that for any cubic integer α, there is a natural number n such that α + n is a chromatic root. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|