zbMATH — the first resource for mathematics

Some families of chromatically unique bipartite graphs. (English) Zbl 0958.05054
Summary: A graph is said to be chromatically unique (or \(\chi\)-unique) if it is uniquely determined by its chromatic polynomial. Let \(K^{-r}(p,q)\) denote the family of graphs obtained from \(K_{p,q}\) by deleting any \(r\) distinct edges. In this paper, we study the chromaticity of the graphs in \(K^{-r}(p,q)\). A sufficient condition is given for a member of \(K^{-r}(p,q)\) to be \(\chi\)-unique and some families of \(\chi\)-unique bipartite graphs are obtained. A conjecture is also proposed.
05C15 Coloring of graphs and hypergraphs
Full Text: DOI
[1] Chao, C.Y.; Whitehead, E.G., On chromatic equivalence of graphs, Springer lecture notes in math, vol. 642, 121-131, (1978)
[2] Giudici, R.E.; Lima de sá, E., Chromatic uniqueness of certain bipartite graphs, (), 69-75 · Zbl 0862.05045
[3] Harary, F., Graph theory, (1969), Addison-Wesley Reading, MA · Zbl 0797.05064
[4] Koh, K.M.; Teo, K.L., The search for chromatically unique graphs, Graphs and combin., 6, 259-285, (1990) · Zbl 0727.05023
[5] K.M. Koh; K.L. Teo, The search for chromatically unique graphs II, preprint. · Zbl 0879.05031
[6] Peng, Y.H., On the chromatic uniqueness of certain bipartite graphs, Discrete math., 94, 129-140, (1991) · Zbl 0752.05030
[7] 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
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.