zbMATH — the first resource for mathematics

On the chromatic uniqueness of certain bipartite graphs. (English) Zbl 0752.05030
A graph \(G\) is chromatically unique if any other graph with the same chromatic polynomial is isomorphic to \(G\). For example, it is known that the complete bipartite graph \(K(n,m)\) is chromatically unique provided \(n,m\geq 2\), as is the complete graph minus a single edge \(K^{-1}(n,m)\) provided \(n,m\geq 3\).
In this paper the author extends the investigation into the chromatic uniqueness of complete bipartite graphs minus 2, 3, or 4 edges. Let \(K^{-r}(n,m)\) denote the class of complete bipartite graphs \(K(n,m)\) with \(r\) edges removed. There are 3 graphs in \(K^{-r}(n,m)\) when \(r=2\), 6 graphs when \(r=3\), and 16 graphs for \(r=4\). The author derives a sufficient condition for a graph in \(K^{-2}(n,m)\) to be chromatically unique. In particular, each such graph is chromatically unique when \(| n-m|\leq 3\). Moreover, graphs with \(| n-m|=d\) are chromatically unique provided that \(n\) is sufficiently large (an explicit polynomial bound is given). In the class \(K^{-3}(m,m)\) any member is chromatically unique provided \(| n-m|\leq 1\) (with a few small exceptions). In \(K^{-4}(n,m)\) any graph is chromatically unique provided \(n=m\geq 4\). Also, each graph in \(K^{-4}(n,n+1)\) is chromatically unique for \(n\geq 5\). A few other results of a similar nature are presented.

05C15 Coloring of graphs and hypergraphs
Full Text: DOI
[1] Behzad, M.; Chartrand, G.; Lesniak-Foster, L., Graphs and digraphs, (1979), Wadsworth Belmont, CA · Zbl 0403.05027
[2] Chao, C.Y.; Whitehead, E.G., Chromatically unique graphs, Discrete math., 27, 171-177, (1979) · Zbl 0411.05035
[3] Chao, C.Y.; Whitehead, E.G., On chromatic equivalence of graphs, (), 121-131
[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.; Goh, B.H.; Koh, K.M., The chromaticity of some families of complete tripartite graphs, Scientia sinica ser., A 1, 1-12, (1988)
[6] Farrell, E.J., On the chromatic coefficients, Discrete math., 29, 257-264, (1980) · Zbl 0443.05041
[7] Frucht, R.W.; Guidici, R.E., Some chromatically unique graphs with seven points, Ars combin., 16A, 161-172, (1983) · Zbl 0536.05026
[8] Guidici, R.E., Some new families of chromatically unique graphs, (), 147-158
[9] Koh, K.M.; Goh, B.H., Two classes of chromatically unique graphs, Discrete math., 82, 13-24, (1990) · Zbl 0697.05027
[10] Y.H. Peng, The chromatic coefficients of a bipartite graph, Ars Combin., to appear. · Zbl 0770.05047
[11] Read, R.C., An introduction to chromatic polynomials, J. combin. theory, 4, 52-71, (1968) · Zbl 0173.26203
[12] Read, R.C.; Tutte, W.T., Chromatic polynomials, (), 15-42 · Zbl 0667.05022
[13] Salzberg, P.M.; Lopez, M.A.; Guidici, R.E., On the chromatic uniqueness of bipartite graphs, Discrete math., 58, 285-294, (1986) · Zbl 0594.05034
[14] 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
[15] Tomescu, I., On 3-coloring of bipartite p-threshold graphs, J. graph theory, 11, 327-338, (1987) · Zbl 0662.05024
[16] Whitehead, E.G.; Zhao, L.C., Cutpoints and the chromatic polynomial, J. graph theory, 8, 371-377, (1984) · Zbl 0551.05041
[17] Whitney, H., The colouring of graphs, Ann. math., 33, 688-718, (1932) · JFM 58.0606.01
[18] Woodall, D.R., Zeros of chromatic polynomials, (), 199-223 · Zbl 0357.05044
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.