# zbMATH — the first resource for mathematics

On the structure and chromaticity of graphs in which any two colour classes induce a tree. (English) Zbl 0893.05004
Some families of chromatically unique graphs are constructed through the partition of the vertex set of a graph $$G$$ into independent sets $$A_1,A_2, \dots,A_r$$ such that the subgraph of $$G$$ induced by $$A_i \cup A_j$$ is a tree for all $$i$$ and $$j$$ with $$1\leq i<j \leq r$$.

##### MSC:
 05C15 Coloring of graphs and hypergraphs 05C05 Trees
##### Keywords:
chromatically unique graphs; partition; tree
Full Text:
##### References:
 [1] Biggs, N., Algebraic graph theory, (1974), Cambridge Univ. Press Cambridge · Zbl 0284.05101 [2] Chao, C.Y.; Li, N.-Z.; Xu, S.-J., On q-trees, J. graph theory, 10, 129-136, (1986) · Zbl 0591.05021 [3] Chao, C.Y.; Whitehead, E.G., Chromatically unique graphs, Discrete math., 27, 171-177, (1979) · Zbl 0411.05035 [4] Chia, G.L., The chromaticity of wheels with a missing spoke, Discrete math., 82, 209-212, (1990) · Zbl 0712.05025 [5] Chia, G.L., On the join of graphs and chromatic uniqueness, J. graph theory, 19, 251-261, (1995) · Zbl 0819.05027 [6] Dirac, G.A., On rigid circuit graphs, Abh. math. sem. univ. Hamburg, 25, 71-76, (1967) · Zbl 0098.14703 [7] Erdős, P., On the number of complete subgraphs contained in certain graphs, Publ. math. inst. hung. acad. sci., 7, 459-464, (1962) [8] Fisher, D.C., Lower bounds on the number of triangles in a graph, J. graph theory, 13, 505-512, (1989) · Zbl 0673.05046 [9] Han, B.T., Chromaticity of qk-trees, Acta math. appl. sinica, 11, 457-467, (1988), (Chinese, English summary) · Zbl 0666.05032 [10] Koh, K.M.; Teo, K.L., The search for chromatically unique graphs, Graphs combin., 6, 259-285, (1990) · Zbl 0727.05023 [11] Koh, K.M.; Teo, K.L., The search for chromatically unique graphs II, Discrete math., 172, 59-78, (1997) · Zbl 0879.05031 [12] Lovàsz, L.; Simonovits, M., On complete subgraphs of a graph II, Stud. pure math., 459-496, (1983) [13] Read, R.C.; Tutte, W.T., Chromatic polynomials, (), 15-42 · Zbl 0667.05022 [14] Vaderlind, P., Chromatic uniqueness of k-trees, () [15] Whitney, H., A logic expansion in mathematics, Bull. amer. math. soc., 38, 572-579, (1932) · JFM 58.0605.08 [16] 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.