×

zbMATH — the first resource for mathematics

Two classes of chromatically unique graphs. (English) Zbl 0697.05027
The chromatic polynomial of a graph G is denoted by P(G;\(\lambda)\). Then G is said to be chromatically unique if: whenever \(P(H;\lambda)=P(G;\lambda)\), then the graph H is isomorphic to G. In this paper, two new classes of chromatically unique graphs are presented. One of these is obtained from disjoint \(K_ r\) (r\(\geq 3)\) and \(C_ s\) (s\(\geq 3)\) by identifying \(e_ 1\in E(K_ r)\) with \(e_ 2\in C_ s\). The other is obtained, for \(n\geq r+1\geq 5\) (with two exceptions corresponding to \((n,r)=(6,4)\) and (7,4)), from disjoint \(K_ r\) and a graph X of order n which is a \(K_ 4\) homeomorph, by identifying \(K_ 3\) in \(K_ r\) with \(K^ 1_ 3\) in X.
Reviewer: A.T.White

MSC:
05C15 Coloring of graphs and hypergraphs
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bari, R.A.; Hall, D.W., Chromatic polynomials and Whitney’s broken circuits, J. graph theory, 1, 269-275, (1977) · Zbl 0387.05014
[2] Birkhoff, G.D.; Lewis, D.C., Chromatic polynomials, Trans. amer. math. soc., 60, 355-451, (1946) · Zbl 0060.41601
[3] Bondy, J.A.; Murty, U.S.R., Graph theory with applications, (1976), MacMillan · Zbl 1134.05001
[4] Chao, C.Y.; Novacky, G.A., On maximally saturated graphs, Discrete math., 41, 139-143, (1982) · Zbl 0495.05023
[5] Chao, C.Y.; Whitehead, E.G., On chromatic equivalence of graphs, (), 121-131
[6] Chao, C.Y.; Whitehead, E.G., Chromatically unique graphs, Discrete math., 27, 171-177, (1979) · Zbl 0411.05035
[7] Chao, C.Y.; Zhao, L.C., Chromatic polynomials of a family of graphs, Ars combinatoria, 15, 111-129, (1983) · Zbl 0532.05027
[8] Chia, G.L., A note on chromatic uniqueness of graphs, J. graph theory, 10, 541-543, (1986) · Zbl 0616.05035
[9] G.L. Chia, Some remarks on the chromatic uniqueness of graphs, to appear in Ars Combinatoria. · Zbl 0672.05033
[10] Chia, G.L.; Goh, B.H.; Koh, K.M., The chromaticity of some families of complete tripartite graphs, Scientia, A:mathematics, 1, 1-12, (1988)
[11] Farrell, E.J., On chromatic coefficients, Discrete math., 29, 257-264, (1980) · Zbl 0443.05041
[12] Giudici, R.E., Some new families of chromatically unique graphs, (), 147-159
[13] Giudici, R.E.; Vinke, R.M., J. comb., Inf. & syst. sci., 5, 323-350, (1980), A table of chromatic polynomials
[14] Loerinc, B., Chromatic uniqueness of the generalized θ-graph, Discrete math., 23, 313-316, (1978) · Zbl 0389.05034
[15] Read, R.C., An introduction to chromatic polynomials, J. combinatorial theory, 4, 52-71, (1968) · Zbl 0173.26203
[16] Read, R.C., Connectivity and chromatic uniqueness, Ars combinatoria, 23, 209-218, (1987) · Zbl 0677.05055
[17] Salzberg, P.M.; Lopez, M.A.; Giudici, R.E., On the chromatic uniqueness of bipartite graphs, Discrete math., 58, 285-294, (1986) · Zbl 0594.05034
[18] Whitehead, E.G.; Zhao, L.C., Cutpoints and the chromatic polynomial, J. graph theory, 8, 371-377, (1984) · Zbl 0551.05041
[19] Whitehead, E.G.; Zhao, L.C., Chromatic uniqueness and equivalence of K4 homeomorphs, J. graph theory, 8, 355-364, (1984) · Zbl 0555.05035
[20] Whitney, H., A logical expansion in mathematics, Bull. amer. math. soc., 38, 572-579, (1932) · JFM 58.0605.08
[21] 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.