Chromatic polynomials of complements of bipartite graphs

DOI10.1007/S00373-012-1268-6zbMATH Open1298.05105arXiv1103.1355OpenAlexW2070221764MaRDI QIDQ742569FDOQ742569

Authors: Adam Bohn 

Publication date: 19 September 2014

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

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.

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

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

zbMATH Keywords

algebraic integerschromatic rootschromatic polynomialsbipartite complements

Mathematics Subject Classification ID

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

Cites Work

• Acyclic orientations of graphs
• An introduction to chromatic polynomials
• Title not available (Why is that?)
• Algebraic properties of chromatic roots
• 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
• Title not available (Why is that?)
• 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)