1
$\begingroup$

I am interested in the combinatorics of the linear coefficient of the chromatic polynomials. I have the following questions.

  1. What are some class of graphs for which it is possible to calculate this number explicitly? For example, Trees, Complete graph, and Cycles. How to calculate this number in general?

  2. What are some interesting combinatorics of this number?

Kindly share some references.

Thank you.

Improve this question
$\endgroup$
5
  • 3
    $\begingroup$ See math.stackexchange.com/questions/2009611/… and around. $\endgroup$
    – user64494
    Commented Aug 1, 2019 at 7:20
  • 1
    $\begingroup$ Seeing the chromatic polynomials of trees, complete graphs and cycles are known, finding the linear term is not so hard. As @user64495 has linked to, the best combinatorial interpretation is that the linear term is the number of acyclic orientations with a single source vertex. $\endgroup$
    – Gordon Royle
    Commented Aug 1, 2019 at 12:49
  • 4
    $\begingroup$ To clarify, "a single source vertex" means that for any fixed vertex $v$, the linear term (up to sign) is the number of acyclic orientations with single source vertex $v$. It is not a priori clear that this number is independent of $v$, $\endgroup$
    – Richard Stanley
    Commented Aug 1, 2019 at 13:31
  • $\begingroup$ @RichardStanley Indeed - I knew what I meant, but what I actually wrote was not very precise. $\endgroup$
    – Gordon Royle
    Commented Aug 1, 2019 at 13:44
  • $\begingroup$ Thanks a lot. your comments were helpful and lead to some good references. $\endgroup$
    – GA316
    Commented Aug 1, 2019 at 16:34

0

Reset to default

You must log in to answer this question.