×

zbMATH — the first resource for mathematics

The search for chromatically unique graphs. II. (English) Zbl 0879.05031
Summary: This expository paper gives a survey on most of the work done on chromatically unique graphs that have been published since our first survey on the subject in [Graphs Comb. 6, No. 3, 259-285 (1990; Zbl 0727.05023)]. Some of the new and relevant results on chromatic equivalence classes are also included. Special techniques and ideas used to produce new chromatically unique graphs or chromatic equivalence classes are highlighted.

MSC:
05C15 Coloring of graphs and hypergraphs
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Behzad, M.; Chartrand, G.; Lesniak-Foster, L., Graphs and digraphs, (1979), Prindle, Weber & Schmidt Boston, MA · Zbl 0403.05027
[2] Borowiecki, M.; Drgas-Burchardt, E., Classes of chromatically unique graphs, Discrete math., 111, 71-75, (1993) · Zbl 0788.05040
[3] Chao, C.Y.; Li, N.Z., On trees of polygons, Arch. math., 45, 180-185, (1985) · Zbl 0575.05027
[4] Chen, X.E.; Bao, X.W.; Ouyang, K.Z., Chromaticity of the graph θ(a, b, c, d), J. shanxi normal univ., 20, 75-79, (1992), (in Chinese, English summary)
[5] Chen, X.E.; Ouyang, K.Z., Chromatic classes of certain 2-connected (n, n + 2)-graphs, J. Lanzhou univ. (natural sc.), 28, 183-184, (1992) · Zbl 0881.05049
[6] Chia, G.L., The chromaticity of wheels with a missing spoke, Discrete math., 82, 209-212, (1990) · Zbl 0712.05025
[7] Chia, G.L., On the chromatic uniqueness of K(1, p2, …, pn), (1992), personal communication
[8] Chia, G.L., On the join of graphs and chromatic uniqueness, J. graph theory, 19, 251-261, (1995) · Zbl 0819.05027
[9] Chia, G.L., The chromaticity of wheels with a missing spoke II, Discrete math., 148, 305-310, (1996) · Zbl 0838.05052
[10] Dirac, G.A., A property of 4-chromatic graphs and some results on critical graphs, J. London math. soc., 27, 85-92, (1952) · Zbl 0046.41001
[11] Dong, F.M., On the uniqueness of chromatic polynomial of generalized wheel graph, J. math. res. exposition, 10, 447-454, (1990), (in Chinese, English summary) · Zbl 0774.05038
[12] Dong, F.M., The chromatic uniqueness of two classes of special graphs, Acta math. sinica, 34, 242-251, (1991), (in Chinese) · Zbl 0753.05034
[13] Dong, F.M., On chromatic uniqueness of two infinite families of graphs, J. graph theory, 17, 387-392, (1993) · Zbl 0777.05059
[14] 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., in press. · Zbl 0893.05004
[15] F.M. Dong and K.M. Koh, On graphs in which any pair of colour classes but one induces a tree, Discrete Math., in press. · Zbl 0874.05023
[16] F.M. Dong and Y.P. Liu, All wheels with two missing consecutive spokes are chromatically unique, Discrete Math., in press. · Zbl 0957.05043
[17] Dong, F.M.; Liu, Y.P., On the chromatic uniqueness of the graph W(n, n − 2, k), Graphs and combinatorics, 12, 221-230, (1996) · Zbl 0857.05039
[18] Dong, F.M.; Liu, Y.P., On the chromatic uniqueness of the join W(n, n − 2) + kk, Discrete math., 145, 95-103, (1995)
[19] F.M. Dong, Y.P. Liu and K.M. Koh, The chromaticity of odd wheels with a missing chord, New Zealand J. Math., in press. · Zbl 0880.05038
[20] Du, Q.Y., On σ-polynomials and a class of chromatically unique graphs, Discrete math., 115, 153-165, (1993) · Zbl 0774.05039
[21] Du, Q.Y., Chromaticity of the complements of paths and cycles, (1994), preprint
[22] Du, Q.Y., On σ-equivalence and χ-equivalence of graphs, J. graph theory, 21, 211-217, (1996) · Zbl 0838.05050
[23] Duffin, R.J., Topology of series-parallel networks, J. math. anal. appl., 10, 303-318, (1965) · Zbl 0128.37002
[24] E.J. Farrell and J.M. Guo, On the characterizing properties of the matching polynomial, to appear. · Zbl 0880.05072
[25] Farrell, E.J.; Whitehead, E.G., Connections between matching and chromatic polynomials, Internat. J. math. math. sci., 15, 757-766, (1992) · Zbl 0799.05053
[26] Giudici, R.E.; Lima de Sá, E., Chromatic uniqueness of certain bipartite graphs, (), 69-75 · Zbl 0862.05045
[27] Giudici, R.E.; Margalio, C., Chromaticity of supercycles of four cells, (), 185-198
[28] Guo, Z.Y.; Li, N.Z., The m-clique polynomial and its application to chromatic polynomials, (), 331-341 · Zbl 0751.05038
[29] Guo, Z.Y.; Li, Y.J., Chromatic uniqueness of complement of the cycles union, J. Wuhan urban construction institute, 6, 1-9, (1989), (in Chinese, English summary)
[30] Koh, K.M.; Teo, C.P., The chromatic uniqueness of graphs related to broken wheels, () · Zbl 0752.05029
[31] Koh, K.M.; Teo, C.P., Some results on chromatically unique graphs, (), 258-262 · Zbl 0940.05502
[32] Koh, K.M.; Teo, C.P., The chromatic uniqueness of certain broken wheels, Discrete math., 96, 65-69, (1991) · Zbl 0752.05029
[33] Koh, K.M.; Teo, C.P., Chromaticity of series-parallel graphs, Discrete math., 154, 289-295, (1996) · Zbl 0856.05035
[34] Koh, K.M.; Teo, K.L., The search for chromatically unique graphs, Graphs combin., 6, 259-285, (1990) · Zbl 0727.05023
[35] Koh, K.M.; Teo, K.L., Chromatic classes of 2-connected (n, n + 3)-graphs with at least two triangles, Discrete math., 127, 243-258, (1994) · Zbl 0796.05033
[36] Li, N.Z.; Liu, R.Y., The chromaticity of the complete t-partite graph K(1, p2,…, pt), J. xinjiang univ. natur. sci., 7, 95-96, (1990)
[37] Li, N.Z.; Whitehead, E.G., The chromaticity of certain graphs with five triangles, Discrete math., 122, 365-372, (1993) · Zbl 0787.05040
[38] Li, W.M., Some new results on chromatic uniqueness of K4 homeomorphs, Math. appl., 4, 43-47, (1991), (in Chinese, English summary)
[39] Liu, R.Y., Chromatic uniqueness of Kn − E(kp5 ∪ rpt), J. system sci. math. sci., 12, 207-214, (1992), (in Chinese, English summary)
[40] Liu, R.Y., Chromatic uniqueness of complementary graph of Pq−1, Pure appl. math., 9, Suppl. 2, 86-87, (1993)
[41] R.Y. Liu, Adjoint polynomials and chromatically unique graphs, Discrete Math., in press. · Zbl 0878.05030
[42] R.Y. Liu and Z.Q. Chen, Two new classes of chromatically unique graphs, to appear.
[43] Liu, R.Y.; Li, N.Z., Chromatic uniqueness of connected vertex-transitive graphs, Math. appl., 4, 50-53, (1991), (in Chinese, English summary) · Zbl 0891.05033
[44] R.Y. Liu and N.Z. Li, A family of chromatically unique graphs of the form K4 − E(G), J. Math. (Wuhan), in press (in Chinese).
[45] Liu, R.Y.; Wang, J.F., On chromatic uniqueness of complement of union of cycles and paths, Theoret. comput. sci. (China), 1, 112-126, (1993), (in Chinese, English summary)
[46] Peng, Y.H., Chromatic uniqueness of certain K(2,4) homeomorphs (bahasa Malaysia), Matematika, 7, 101-111, (1991)
[47] Peng, Y.H., On the chromatic uniqueness of certain bipartite graphs, Discrete math., 94, 129-140, (1991) · Zbl 0752.05030
[48] Peng, Y.H., New infinite families of chromatically unique graphs, sains malaysiana, Quantitative studies, 21, 15-25, (1992)
[49] Peng, Y.H., Three families of chromatically unique graphs, Serdica, 18, 10-16, (1992) · Zbl 0808.05050
[50] Peng, Y.H., On the chromatic coefficients of a bipartite graph ars, Combin., 34, 107-117, (1992) · Zbl 0770.05047
[51] Peng, Y.H., On the chromatic coefficients of a graph and chromatic uniqueness of certain n-partition graphs, (), 307-316, Beijing, 1993
[52] Peng, Y.H., Another family of chromatically unique graphs, Graphs combin., 11, 285-291, (1995) · Zbl 0836.05028
[53] Y.H. Peng, C.H.C. Little, K.L. Teo and H. Wang, Chromatic equivalence classes of certain generalized polygonal trees, Discrete Math., in press. · Zbl 0883.05058
[54] Read, R.C., Broken wheels are SLC, Ars combin., 21A, 123-128, (1986) · Zbl 0597.05033
[55] Teo, C.P.; Koh, K.M., The chromaticity of complete bipartite graphs with at most one edge deleted, J. graph theory, 14, 89-99, (1990) · Zbl 0712.05027
[56] Teo, C.P.; Koh, K.M., The number of shortest cycles and the chromatic uniqueness of a graph, J. graph theory, 16, 7-15, (1992) · Zbl 0770.05064
[57] Teo, C.P.; Koh, K.M., On chromatic-uniqueness of uniform subdivisions of graphs, Discrete math., 128, 327-335, (1994) · Zbl 0796.05034
[58] Teo, K.L.; Koh, K.M., Chromatic classes of certain 2-connected (n, n + 2)-graphs, Ars combin., 32, 65-76, (1991) · Zbl 0760.05044
[59] Tomescu, I., On the sum of all distances in chromatic blocks, J. graph theory, 18, 83-102, (1994) · Zbl 0789.05036
[60] Wakelin, C.D.; Woodall, D.R., Chromatic polynomials, polygon trees, and outerplanar graphs, J. graph theory, 16, 459-466, (1992) · Zbl 0778.05074
[61] Whitehead, E.G., Chromatic polynomials of generalized trees, Discrete math., 72, 391-393, (1988) · Zbl 0659.05045
[62] Xu, S., The chromatic uniqueness of complete bipartite graphs, Discrete math., 94, 153-159, (1991) · Zbl 0752.05031
[63] Xu, S., Chromaticity of a family of K4-homeomorphs, Discrete math., 117, 293-297, (1993) · Zbl 0781.05022
[64] Xu, S., Classes of chromatically equivalent graphs and polygon trees, Discrete math., 133, 267-278, (1994) · Zbl 0813.05030
[65] Xu, S.J.; Liu, J.J.; Peng, Y.H., The chromaticity of s-bridge graphs and related graphs, Discrete math., 135, 349-358, (1994) · Zbl 0814.05036
[66] C.F. Ye and R.Y. Liu, Chromatic uniqueness of a new family of graphs, Pure Appl. Math., in press.
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.