×

zbMATH — the first resource for mathematics

Chromatic classes of 2-connected \((n,n+3)\)-graphs with at least two triangles. (English) Zbl 0796.05033
Two graphs \(G\) and \(H\) are said to be chromatically equivalent if their chromatic polynomials are the same. A graph \(G\) is said to be chromatically unique if every graph chromatically equivalent to \(G\) is isomorphic to \(G\). Let \(C\) denote the class of all 2-connected graphs of order \(n\) and size \(n+3\) having at least two 3-cycles. In this paper all equivalence classes in \(C\) under the equivalence relation of chromatic equivalence are determined; the structure of the graphs in each class is characterized; new families of chromatically equivalent and chromatically unique graphs are produced.

MSC:
05C15 Coloring of graphs and hypergraphs
05C38 Paths and cycles
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Chao, C. Y.; Whitehead, E. G., Chromatically unique graphs, Discrete Math., 27, 171-177, (1979) · Zbl 0411.05035
[2] Chao, C. Y.; Zhao, L. C., Chromatic polynomials of a family of graphs, Ars Combin., 15, 111-129, (1983) · Zbl 0532.05027
[3] Farell, E. J., On chromatic coefficients, Discrete Math., 29, 257-264, (1980) · Zbl 0443.05041
[4] Koh, K. M.; Goh, B. H., Two classes of chromatically unique graphs, Discrete Math., 82, 13-24, (1990) · Zbl 0697.05027
[5] Li, W. M., Almost every K_4-homeomorph is chromatically unique, Ars Combin., 23, 13-36, (1987) · Zbl 0644.05020
[6] Loerinc, B., Chromatic uniqueness of the generalized θ-graphs, Discrete Math., 23, 313-316, (1978) · Zbl 0389.05034
[7] Read, R. C., An introduction to chromatic polynomials, J. Combin. Theory, 4, 52-71, (1968) · Zbl 0173.26203
[8] 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
[9] Whitehead, E. G.; Zhao, L. C., Cutpoints and the chromatic polynomial, J. Graph Theory, 8, 371-377, (1984) · Zbl 0551.05041
[10] Whitehead, E. G.; Zhao, L. C., Chromatic uniqueness and equivalence of K_4 homeomorphs, J. Graph Theory, 8, 355-364, (1984) · Zbl 0555.05035
[11] Whitney, H., A logical expansion in mathematics, Bull. Amer. Math. Soc., 38, 572-579, (1932) · JFM 58.0605.08
[12] Whitney, H., The colouring of graphs, Ann. Math., 33, 688-718, (1932) · JFM 58.0606.01
[13] Woodall, D. R., Zeros of chromatic polynomials, combinational surveys, (Cameron, P. J., Proc. 6th British Comb. Conf., (1977), Academic Press New York), 199-223 · Zbl 0357.05044
[14] Zykov, A. A., On some properties of linear complexes, Amer. Math. Soc. Transl., 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.