zbMATH — the first resource for mathematics

On graphs in which any pair of colour classes but one induces a tree. (English) Zbl 0874.05023
For \(m\geq 3\), let \({\mathcal F}_m\) be the family of graphs \(G\) that possesses an independent set partition \(\{A_1,\ldots,A_m\}\) such that the subgraphs of \(G\) induced by \(A_i\cup A_j\) are trees except one, which is a forest having two components. In this paper it is shown that for each \(G\) of order \(n\) in \({\mathcal F}_m\), \(t(G)\leq f(n,m)=\frac{1}{3}(3n-2m) {{m-1} \choose {2}}-m+2\), where \(t(G)\) denotes the number of triangles in \(G\). Let \(\rho(G)=f(n,m)-t(G)\). The graphs in \({\mathcal F}_m\) with \(\rho(G)=0\) and the graphs in \({\mathcal F}_3\) with \(\rho(G)=1\) are characterized. By applying the first characterization, it is deduced that a graph \(G\) of order \(n\geq m\) is in \({\mathcal F}_m\) with \(\rho(G)=0\) iff its chromatic polynomial is given by \(\lambda(\lambda-1)\cdots(\lambda-m+3)(\lambda-m+2)^2(\lambda-m+1)^{n-m}\). By applying the second characterization it is shown that the graphs obtained from the wheels of even order by deleting two consecutive spokes are uniquely determined by their chromatic polynomials, which solves partially Problem 4 in K. M. Koh and K. L. Teo [Graphs Comb. 5, No. 3, 259-285 (1990; Zbl 0727.05023)].

05C15 Coloring of graphs and hypergraphs
05C75 Structural characterization of families of graphs
05C38 Paths and cycles
05C35 Extremal problems in graph theory
Full Text: DOI
[1] Chao, C.Y.; Li, N.-Z.; Xu, S.-J., On q-trees, J. graph theory, 10, 129-136, (1986) · Zbl 0591.05021
[2] Chia, G.L., The chromaticity of wheels with a missing spoke, Discrete math., 82, 209-212, (1990) · Zbl 0712.05025
[3] Dirac, G.A., On rigid circuit graphs, Abh. math. sem. univ. Hamburg, 25, 71-76, (1967) · Zbl 0098.14703
[4] F.M. Dong and K.M. Koh, On the structure and chromaticity of graphs in which any two colour classes induce a tree, Discrete Math., to appear. · Zbl 0893.05004
[5] Erdös, P., On the number of complete subgraphs contained in certain graphs, Pub. math. institute hung, acad. sci., 7, 459-464, (1962) · Zbl 0116.01202
[6] Fisher, D.C., Lower bounds on the number of triangles in a graph, J. graph theory, 13, 505-512, (1989) · Zbl 0673.05046
[7] Koh, K.M.; Teo, K.L., The search for chromatically unique graphs, Graphs and combin., 6, 259-285, (1990) · Zbl 0727.05023
[8] K.M. Koh and K.L. Teo, The search for the chromatically unique graphs II, Discrete Math., to appear. · Zbl 0879.05031
[9] Li, N.-Z.; Whitehead, E.G., The chromatic uniqueness of W10, Discrete math., 104, 197-199, (1992)
[10] Lovàsz, L.; Simonovits, M., On complete subgraphs of a graph II, studies pure math, (), 459-496
[11] Read, R.C., A note on the chromatic uniqueness of W10, Discrete math., 69, 317, (1988) · Zbl 0639.05019
[12] Read, R.C.; Tutte, W.T., Chromatic polynomials, (), 15-42 · Zbl 0667.05022
[13] Wanner, T., On the chromaticity of certain subgraphs of a q-tree, J. graph theory, 13, 597-605, (1989) · Zbl 0698.05029
[14] Whitney, H., A logic expansion in mathematics, Bull. amer. math. soc., 38, 572-579, (1932) · JFM 58.0605.08
[15] Xu, S.-J.; Li, N.-Z., The chromaticity of wheels, Discrete math., 51, 207-212, (1984) · Zbl 0547.05032
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.