zbMATH — the first resource for mathematics

Chromatic polynomials of connected graphs. (English) Zbl 0535.05053
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\).

05C99 Graph theory
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
05C15 Coloring of graphs and hypergraphs
05C40 Connectivity
Full Text: DOI
[1] C.-Y. Chao andL.-C. Zhao, Chromatic polynomials of a family of graphs. Ars Combinatoria15, 111-129 (1983). · Zbl 0532.05027
[2] O.Ore, The four-color problem. New York 1967. · Zbl 0149.21101
[3] R. C. Read, An introduction to chromatic polynomials. J. Comb. Theory4, 52-71 (1968). · Zbl 0173.26203 · doi:10.1016/S0021-9800(68)80087-0
[4] E. G.Whitehead, Jr., and L.-C.Zhao, Cutpoints and the chromatic polynomial. To appear in J. Graph Theory. · Zbl 0551.05041
[5] H. Whitney, The coloring of graphs. Ann. of Math.73, 688-718 (1932). · JFM 58.0606.01 · doi:10.2307/1968214
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.