×

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.

MSC:

05C15 Coloring of graphs and hypergraphs
PDFBibTeX XMLCite
Full Text: DOI

References:

[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, (Congr. Numer., 76 (1990)), 69-75 · Zbl 0862.05045
[3] Harary, F., Graph Theory (1969), Addison-Wesley: 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.; 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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.