Acyclic orientations and chromatic generating functions
Let \(P_G(k)\) be the chromatic polynomial of a graph \(G\) with \(n\geq 2\) vertices, none of which is isolated. Let \(R_G(k)= P_G(k)/k(k+1)\). Now fix two adjacent vertices \(a\) and \(z\) in \(G\). Let \({\mathcal O}\) be an acyclic orientation of \(G\) having \(a\) as a source and \(z\) as a sink. A function \(f: V(G)\to \{0,1,\dots, k\}\) is \({\mathcal O}\)-compatible if: (i) if \((i,j)\) is an edge of \({\mathcal O}\), then \(f(i)\leq f(j)\); (ii) \(f(a)= 0\) and \(f(z)= k\); (iii) if \(s\) is another source of \({\mathcal O}\), then \(f(s)> 0\); and (iv) if \(t\) is another sink of \({\mathcal O}\), then \(f(t)< k\). The author shows that the coefficients of the polynomial \[ (1- t)^{n- 1}\sum^\infty_{k= 1} R_G(k) t^k \] are nonnegative and, in turn, that if \(k\) is a nonnegative integer then \((-1)^n R_G(-k)\) is the number of pairs \(({\mathcal O},f)\) such that \({\mathcal O}\) is an acyclic orientation of \(G\) in which \(a\) is a source and \(z\) is a sink, and \(f\) is an \({\mathcal O}\)-compatible function from \(V(G)\) to \(\{0,1,\dots, k\}\).
- Acyclic orientations and the chromatic polynomial
- Acyclic and oriented chromatic numbers of graphs
- Acyclic orientation polynomials and the sink theorem for chromatic symmetric functions
- Acyclic orientation polynomials and the sink theorem for chromatic symmetric functions
- Proving a conjecture on chromatic polynomials by counting the number of acyclic orientations
- Bounds on the chromatic polynomial and on the number of acyclic orientations of a graph
- Chromatic polynomials of oriented graphs
- Graph colorings and acyclic orientations
- Complete oriented colourings and the oriented achromatic number
- Orientations of graphs with uncountable chromatic number
- Graph coloring and monotone functions on posets
- The topology of the coloring complex
- Binomial inequalities for chromatic, flow, and tension polynomials
- Acyclic orientations of graphs. (Reprint)
- The chromatic generating function
- Complete oriented colourings and the oriented achromatic number
- Enumeration of Golomb rulers and acyclic orientations of mixed graphs
- A combinatorial description of finite O-sequences and ACM genera
- Acyclic orientation polynomials and the sink theorem for chromatic symmetric functions
- Notes on acyclic orientations and the shelling lemma
- Acyclic orientations and the chromatic polynomial
- Interview with Xavier Viennot
- Combinatorial Generation via Permutation Languages. V. Acyclic Orientations
- The active bijection for graphs
- Combinatorial reciprocity for the chromatic polynomial and the chromatic symmetric function
- Set maps, umbral calculus, and the chromatic polynomial
This page was built for publication: Acyclic orientations and chromatic generating functions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5937454)