Proof of a chromatic polynomial conjecture
Let \(P(G,\lambda)\) be the chromatic polynomial of a graph \(G\) (i.e., the number of mappings \(f\) from the vertex set of \(G\) to \(\{1,2,\dots, \lambda\}\) such that \(f(x)\neq f(y)\) whenever \(x\) and \(y\) are adjacent vertices in \(G\) if \(\lambda\) is a positive integer). We prove a conjecture on chromatic polynomials proposed by \textit{J. E. Bartels} and \textit{D. J. A. Welsh} [Lect. Notes Comp. Sci. 920, 373-387 (1995)]: \(P(G, n)(P(G, n-1))^{-1}\geq n^n/(n- 1)^n> e\), where \(n\) is the number of vertices in \(G\) and \(e\) is the base of the natural logarithm.
- The chromatic polynomial and list colorings
- Two chromatic polynomial conjectures
- Bounds for mean colour numbers of graphs
- A note on the shameful conjecture
- On the chromatic polynomial of a graph
- Mean color numbers of some graphs
- Some inequalities on chromatic polynomials
- A proof from The Book: a lower bound for the polychromatic number of the plane
- Chromatic polynomials of simplicial complexes
- scientific article; zbMATH DE number 4156470 (Why is no real title available?)
- On Brenti's conjecture about the log-concavity of the chromatic polynomial
- scientific article; zbMATH DE number 1512685 (Why is no real title available?)
- On the degree-chromatic polynomial of a tree
- Problems on chromatic polynomials of hypergraphs
- The chromatic polynomial for cycle graphs
- On the degree-chromatic polynomial of a tree
- Proving a conjecture on chromatic polynomials by counting the number of acyclic orientations
- Dominic Welsh: his work and influence
- Counting packings of list-colorings of graphs
- Proof of a conjectured lower bound on the chromatic number of a graph
This page was built for publication: Proof of a chromatic polynomial conjecture
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1569069)
