Chromatic polynomials of complements of bipartite graphs

DOI10.1007/S00373-012-1268-6MaRDI QIDQ742569zbMATH OpenOpenAlexFDO

Authors Adam Bohn

Publication date 19 September 2014

Published in Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1103.1355

zbMATH Keywords

algebraic integerschromatic rootschromatic polynomialsbipartite complements

Mathematics Subject Classification ID

Graph polynomials (05C31) Coloring of graphs and hypergraphs (05C15)

Abstract: Bicliques are complements of bipartite graphs; as such each consists 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 $alpha+n$ conjecture, by showing that for any cubic integer $alpha$, there is a natural number $n$ such that $alpha+n$ is a chromatic root.

Recommendations

• An algorithm which outputs a graph with a specified chromatic factor
• Chromatic roots as algebraic integers
• Algebraic properties of chromatic roots
• Bivariate chromatic polynomials in computer algebra
• scientific article; zbMATH DE number 27256

Cites work

• scientific article; zbMATH DE number 3679828 (Why is no real title available?)
• Acyclic orientations of graphs
• Algebraic properties of chromatic roots
• An introduction to chromatic polynomials
• Complementary matching vectors and the uniform matching extension property
• Connections between the matching and chromatic polynomials

Cited in

(10)

• Algebraic properties of chromatic roots
• An algorithm which outputs a graph with a specified chromatic factor
• An extension of the bivariate chromatic polynomial
• An infinite family of 2-connected graphs that have reliability factorisations
• CHROMATIC POLYNOMIALS AND BIALGEBRAS OF GRAPHS
• scientific article; zbMATH DE number 7593849 (Why is no real title available?)
• A chromatic partition polynomial
• Bivariate chromatic polynomials in computer algebra
• p-adic roots of chromatic polynomials
• An attempt to classify bipartite graphs by chromatic polynomials

This page was built for publication: Chromatic polynomials of complements of bipartite graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q742569)