New expressions for order polynomials and chromatic polynomials

DOI10.1002/JGT.22505zbMATH Open1495.05139arXiv1909.02310OpenAlexW2981773644MaRDI QIDQ5110675

Publication date: 21 May 2020

Published in: Journal of Graph Theory (Search for Journal in Brave)

Abstract: Let

G = (V, E)

be a simple graph with

V = 1, 2, c d o t s, n

and

c h i (G, x)

be its chromatic polynomial. For an ordering

p i = (v_{1}, v_{2}, c d o t s, v_{n})

of elements of

V

, let

d e l t a_{G} (p i)

be the number of

i

's, where

1 l e i l e n - 1

, with either

v_{i} < v_{i + 1}

or

v_{i} v_{i + 1} i n E

. Let

c a l W (G)

be the set of subsets

a, b, c

of

V

, where

a < b < c

, which induces a subgraph with

a c

as its only edge. We show that

c a l W (G) = e m p t y s e t

if and only if

(- 1)^{n} c h i (G, - x) = s u m_{p i} x + d e l t a_{G} (p i) c h o o s e n

, where the sum runs over all

n!

orderings

p i

of

V

. To prove this result, we establish an analogous result on order polynomials of posets and apply Stanley's work on the relation between chromatic polynomials and order polynomials.

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

zbMATH Keywords

chromatic polynomial order polynomial

Mathematics Subject Classification ID

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