Chromatic polynomials of connected graphs

We divide the family of connected graphs with \(n(\geq 3)\) vertices into 3 mutually disjoint subfamilies, namely, \({\mathcal F}_ 1\) consists of all connected graphs each of which has at least one cutpoint, \({\mathcal F}_ 2\) consists of all 2-connected graphs each of which has no subgraph homeomorphic to the complete graph \(K_ 4\) with 4 vertices, and \({\mathcal F}_ 3\) consists of all 2-connected graphs each of which has at least one subgraph homeomorphic to \(K_ 4\). Let G be a connected graph with \(n(\geq 3)\) vertices, and \(P(G,\lambda)=\lambda^ n-a_{n- 1}\lambda^{n-1}+...\pm a_ 1\lambda\) be its chromatic polynomial. Replacing \(\lambda\) in P(G,\(\lambda)\) by \(\omega +1\), we have \(P(G,\lambda)=Q(G,\omega)=\omega^ n+b_{n-1}\omega^{n-1}+...+b_ 1\omega.\) Here, we show that (1) \(G\in {\mathcal F}_ 1\) if and only if \(| b_ 1| =0\), (2) \(G\in {\mathcal F}_ 2\) if and only if \(| b_ 1| =1\), and (3) \(G\in {\mathcal F}_ 3\) if and only if \(| b_ 1| \geq 2\).

Recommendations

Cites work

Cited in

(22)

This page was built for publication: Chromatic polynomials of connected graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q790846)