1
$\begingroup$

The number of spanning trees $\tau(G)$ of a simple graph $G$ is seen to satisfy the deletion-contraction recurrence: $$\tau(G)=\tau(G-e)+\tau(G.e),$$ where $e$ is an edge of the graph $G$ and $G-e$ denotes the graph $G$ with edge $e$ deleted and $G.e$ denotes the graph $G$ with the edge $e$ contracted.

Now, the chromatic polynomial $P(G)$ also satisfies a similar deletion-contraction relation: $$P(G)=P(G-e)-P(G.e).$$ This gives rise to the question that is there some sort of a relation between the chromatic properties and the number of spanning trees in a graph $G$. Specifically,

  1. Is there a relation between the number of spanning trees and the chromatic number of a graph?

  2. Are they at least asymptotically related?

Thanks beforehand.

Improve this question
$\endgroup$
3
  • 3
    $\begingroup$ Well there's the en.wikipedia.org/wiki/Tutte_polynomial $\endgroup$
    – Sam Hopkins
    Commented Jan 29, 2020 at 15:39
  • $\begingroup$ @SamHopkins thanks, but can we have a relation between the chromatic number and the number of spanning trees as such? $\endgroup$
    – vidyarthi
    Commented Jan 29, 2020 at 16:34
  • 3
    $\begingroup$ No, for example the bipartite graph K_{n,n} has many spanning trees, whereas a 2n vertex graph obtained from a clique on k-1 vertices plus 2n-k isolated vertices, then add a vertex adjacent to all others, has only k^{k-2} spanning trees. Sam Hopkins’ answer is really correct, for note what deletion-contraction is not really finding optimal colourings, it’s counting not necessarily optimal colourings. $\endgroup$
    – user36212
    Commented Jan 29, 2020 at 19:13

0

Reset to default

You must log in to answer this question.