×

zbMATH — the first resource for mathematics

The search for chromatically unique graphs. (English) Zbl 0727.05023
Authors’ abstract: “The number of vertex-colourings of a simple graph G in not more than \(\lambda\) colours is a polynomial in \(\lambda\). This polynomial, denoted by P(G,\(\lambda\)), is called the chromatic polynomial of G. A graph G is said to be chromatically unique, in short \(\chi\)- unique, if \(H\cong G\) for any graph H with \(P(H,\lambda)=P(G,\lambda)\). Since the appearance of the first paper on \(\chi\)-unique graphs by C.-Y. Chao and E. J. Whitehead jun. [Theor. Appl. Graphs, Proc. Kalamazoo 1976, Lect. Notes Math. 642, 121-131 (1978; Zbl 0369.05032)], various families of and several results on such graphs have been obtained successively, especially during the last five years. It is the aim of this expository paper to give a survey on most of the works done on \(\chi\)-unique graphs. A number of related problems and conjectures are also included.”

MSC:
05C15 Coloring of graphs and hypergraphs
05C35 Extremal problems in graph theory
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bari, R.A., Hall, D.W.: Chromatic polynomials and Whitney’s broken circuits. J. Graph Theory1, 269–275 (1977) · Zbl 0387.05014 · doi:10.1002/jgt.3190010307
[2] Behzad, M., Chartrand, G., Lesniak-Foster, L.: Graphs and Digraphs. Wadsworth 1979 · Zbl 0403.05027
[3] Biggs, N.: Algebraic Graph Theory. Cambridge: Cambridge University Press 1974 · Zbl 0284.05101
[4] Birkhoff, G.D.: A determinant formula for the number of ways of coloring a map. Annals of Math.14 (2), 42–46 (1912) · JFM 43.0574.02 · doi:10.2307/1967597
[5] Bondy, J.A., Murty, U.S.R.: Graph theory with applications. MacMillan 1976 · Zbl 1226.05083
[6] Brito, M.R.: On supercycleC(a, b, c). Ars Combinatoria25A, 165–171 (1988) · Zbl 0658.05030
[7] Chao, C.Y., Novacky, Jr. G.A.: On maximally saturated graphs. Discrete Math.41, 139–143 (1982) · Zbl 0495.05023 · doi:10.1016/0012-365X(82)90200-X
[8] Chao, C.Y., Whitehead, Jr. E.G.: On chromatic equivalence of graphs. In: Theory and Applications of Graphs, ed. Alavi, Y. and Lick, D.R., Springer Lecture Notes in Math.642, 121–131 (1978) · doi:10.1007/BFb0070369
[9] Chao, C.Y., Whitehead, Jr. E.G.: Chromatically unique graphs. Discrete Math.27, 171–177 (1979) · Zbl 0411.05035 · doi:10.1016/0012-365X(79)90107-9
[10] Chao, C.Y., Zhao, L.C.: Chromatic polynomials of a family of graphs. Ars Combinatoria15, 111–129 (1983) · Zbl 0532.05027
[11] Chao, C.Y., Zhao, L.C.: Chromatic polynomials of connected graphs. Arch. Math.43, 187–192 (1984) · Zbl 0535.05053 · doi:10.1007/BF01193920
[12] Chia, G.L.: Some remarks on the chromatic uniqueness of graphs. Ars Combinatoria26A, 65–72 (1988) · Zbl 0672.05033
[13] Chia, G.L.: A note on chromatic uniqueness of graphs. J. Graph Theory10, 541–543 (1986) · Zbl 0616.05035 · doi:10.1002/jgt.3190100413
[14] Chia, G.L.: The chromaticity of wheels with a missing spoke, Discrete Math.82, 209–212 (1990) · Zbl 0712.05025 · doi:10.1016/0012-365X(90)90326-D
[15] Chia, G.L.: The Petersen graph is uniquely determined by its chromatic polynomial (preprint)
[16] Chia, G.L., Goh, B.H., Koh, K.M.: The chromaticity of some families of complete tripartite graphs. Scientia, Series A: Mathematical Sciences2, 27–37 (1988) · Zbl 0760.05037
[17] Farrell, E.J.: On chromatic coefficients. Discrete Math.29, 257–264, (1980) · Zbl 0443.05041 · doi:10.1016/0012-365X(80)90154-5
[18] Frucht, R.W.: A new method of computing chromatic polynomials of graphs. In: Analysis, Geometry and Probability (Valporaiso 1981). Lecture Notes in Pure and Appl. Math.96, 69–77 (1985)
[19] Frucht, R.W., Giudici, R.E.: Some chromatically unique graphs with seven points. Ars Combinatoria16A, 161–172 (1983) · Zbl 0536.05026
[20] Giudici, R.E.: Some new families of chromatically unique graphs. Proc. First Chilean Math. Symp., (Valparaiso 1980). Lecture Notes in Pure and Appl. Math.96, 147–158 (1985)
[21] Giudici, R.E., López, M.A.: Chromatic uniqueness of sKW Report No. 85-03, Dpto. de Mat. y Ciencia de la Comp. Univ. Simón Bolivar 1985
[22] Giudici, R.E., Margaglio, C.: Chromatically equivalent graphs. Ars Combinatoria25B, 221–229 (1988) · Zbl 0665.05018
[23] Giudici, R.E., Melián, M.Y.: Chromatic uniqueness of 3-face graphs. Report No.88-05, Dpto. de Mat. y Ciencia de la Comp., Univ. Simón Bolivar 1988
[24] Giudici, R.E., Melián, M.Y.: Chromatic uniqueness of the supercycleC(b, a, a, a) (to appear)
[25] Giudici, R.E., Vinke, R.M.: A table of chromatic polynomials. J. Comb., Inf. and Syst. Sci.5, 323–350 (1980) · Zbl 0454.05026
[26] Gracia, Z., Salzberg, P.M.: Chromatic classification ofK p –G 6. Ars Combinatoria20-B, 107–111 (1985)
[27] Han, B.T.: The chromaticity of graphsK n (1,m). Acta Math. Appl. Sinica9(1), 101–112 (1986) · Zbl 0593.05028
[28] Koh, K.M., Goh, B.H.: Two classes of chromatically unique graphs. Discrete Math.82, 13–24 (1990) · Zbl 0697.05027 · doi:10.1016/0012-365X(90)90041-F
[29] Koh, K.M., Teo, C.P.: The chromatic uniqueness of certain broken wheels. Discrete Math. (To appear) · Zbl 0752.05029
[30] Li, N.Z., Whitehead, Jr. E.G., Xu, S.J.: Classification of chromatically unique graphs having quadratic\(\sigma\)-polynomials. J. Graph Theory11(2, 169–176 (1987) · Zbl 0686.05021 · doi:10.1002/jgt.3190110207
[31] Li, W.M.: Almost everyK 4-homeomorph is chromatically unique. Ars Combinatoria23, 13–36 (1987) · Zbl 0644.05020
[32] Loerinc, B.: Chromatic uniqueness of the generalized\(\theta\)-graphs. Discrete Math.23, 313–316 (1978) · Zbl 0389.05034
[33] Loerinc, B., Whitehead, Jr. E.G.: Chromatic polynomials for regular graphs and modified wheels. J. Comb. Theory, SeriesB 31, 54–61 (1981) · Zbl 0456.05029 · doi:10.1016/S0095-8956(81)80010-X
[34] Read, R.C.: An introduction to chromatic polynomials. J. Combinatorial Theory4, 52–71 (1968) · Zbl 0173.26203 · doi:10.1016/S0021-9800(68)80087-0
[35] Read, R.C.: A note on the chromatic uniqueness ofW 10. Discrete Math.69, 317 (1988) · Zbl 0639.05019 · doi:10.1016/0012-365X(88)90061-1
[36] Read, R.C.: Connectivity and chromatic uniqueness. Ars Combinatoria23, 209–218 (1987) · Zbl 0677.05055
[37] Read, R.C.: On the chromatic properties of graphs up to 10 vertices. Congressus Numerantium59, 243–255 (1987) · Zbl 0648.05021
[38] Read, R.C.,: An improved method for computing the chromatic polynomials of sparse graphs. Research Report CORR 87-20, Dept. of Comb. and Optim., U. of Waterloo (1987)
[39] Read, R.C.: Recent advances in chromatic polynomial theory (to appear)
[40] Read, R.C., Tutte, W.T.: Chromatic polynomials. In: Selected Topics in Graph Theory3, Academic Press, 15–42 (1988)
[41] Salzberg, P.M.: Chromatic classification ofK p –Z for |Edges (Z)| 5 (to appear)
[42] Salzberg, P.M., López, M.A., Giudici, R.E.: On the chromatic uniqueness of bipartite graphs. Discrete Math.58, 285–294 (1986) · Zbl 0594.05034 · doi:10.1016/0012-365X(86)90146-9
[43] Teo, C.P., Koh, K.M.: The chromaticity of complete bipartite graphs with at most one edge deleted. J. Graph Theory14, 89–99 (1990) · Zbl 0712.05027 · doi:10.1002/jgt.3190140110
[44] Teo, K.L., Koh, K.M.: Chromatic classes of certain 2-connected (n, n + 2)-graphs. Ars Combinatoria (to appear) · Zbl 0760.05044
[45] Teo, K.L., Koh, K.M.: Chromatic classes of 2-connected (n, n + 3)-graphs with at least two triangles, Research Report340, Math. Dept., National U. of Singapore (1988) · Zbl 0796.05033
[46] Tomescu, I.: On 3-colorings of bipartitep-threshold graphs. J. Graph Theory11(3, 327–338 (1987) · Zbl 0662.05024 · doi:10.1002/jgt.3190110307
[47] Tutte, W.T.: Chromials. In: Hypergraph seminar 1972. Springer Lecture Notes in Math.411, 243–266 (1974) · doi:10.1007/BFb0066197
[48] Whitehead, Jr. E.G.: Chromatic polynomials for chorded cycles. Proc. 6th S. E. Conf. Comb., Graph Theory and Comp., Congressus Numerantium14, 619–625 (1975) · Zbl 0327.05107
[49] Whitehead, Jr. E.G., Zhao, L.C.: Cutpoints and the chromatic polynomial. J. Graph Theory8, 371–377 (1984) · Zbl 0551.05041 · doi:10.1002/jgt.3190080305
[50] Whitehead, Jr. E.G., Zhao, L.C.: Chromatic uniqueness and equivalence ofK 4 homeomorphs. J. Graph Theory8, 355–364 (1984) · Zbl 0555.05035 · doi:10.1002/jgt.3190080303
[51] Whitney, H.: A logical expansion in mathematics. Bull. Amer. Math. Soc.38, 572–579 (1932) · JFM 58.0605.08 · doi:10.1090/S0002-9904-1932-05460-X
[52] Whitney, H.: The colouring of graphs. Ann. Maths33, 688–718 (1932) · JFM 58.0606.01 · doi:10.2307/1968214
[53] Woodall, D.R.: Zeros of chromatic polynomials. Combinatorial surveys: Proc. 6th British Comb. Conf. (ed. Cameron P.J.), Academic Press, 199–223 (1977) · Zbl 0357.05044
[54] Xu, S.J., Li, N.Z.: The chromaticity of wheels. Discrete Math.51, 207–212 (1984) · Zbl 0547.05032 · doi:10.1016/0012-365X(84)90072-4
[55] Zykov, A.A.: On some properties of linear complexes. Amer. Math. Soc. Transl. No.79 (1952); translated from Math. Sb.24(66), 163–188 (1949)
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.