×
Gein, Pavel A.

On chromatic uniqueness of some complete tripartite graphs. (English) Zbl 1473.05088

Ural Math. J. 7, No. 1, 38-65 (2021).
Summary: Let \(P(G, x)\) be a chromatic polynomial of a graph \(G\). Two graphs \(G\) and \(H\) are called chromatically equivalent iff \(P(G, x) = H(G, x)\). A graph \(G\) is called chromatically unique if \(G\simeq H\) for every \(H\) chromatically equivalent to \(G\). In this paper, the chromatic uniqueness of complete tripartite graphs \(K(n_1, n_2, n_3)\) is proved for \(n_1 \geqslant n_2 \geqslant n_3 \geqslant 2\) and \(n_1 - n_3 \leqslant 5\).

MSC:

05C15 Coloring of graphs and hypergraphs
05C31 Graph polynomials

Keywords:

chromatic uniqueness; chromatic equivalence; complete multipartite graphs; chromatic polynomial
PDF BibTeX XML Cite
\textit{P. A. Gein}, Ural Math. J. 7, No. 1, 38--65 (2021; Zbl 1473.05088)
Full Text: DOI MNR

References:

[1] Asanov M. O., Baransky V. A., Rasin V. V., Diskretnaya matematika: grafy, matroidy, algoritmy [Discrete Mathematics: Graphs, Matroids, Algorithms], “Lan”, Saint-Petersburg, 2010, 364 pp. (in Russian)
[2] Baransky V. A., Koroleva T. A., “Chromatic uniqueness of certain complete tripartite graphs”, Izv. Ural. Gos. Univ. Mat. Mekh. Inform., 74:12 (2010.), 5-26 (in Russian) · Zbl 1323.05044
[3] Baransky V. A., Koroleva T. A., Senchonok T. A., “On the partition lattice of all integers”, Sib. Èlektron. Mat. Izv., 13 (2016), 744-753 (in Russian) · Zbl 1370.05014
[4] Baranskii V. A., Sen’chonok T. A., “Chromatic uniqueness of elements of height \(\leq 3\) in lattices of complete multipartite graphs”, Proc. Steklov Inst. Math., 279 (2012), 1-16 · Zbl 1301.05117
[5] Brylawski T., “The lattice of integer partitions.”, Discrete Math., 6:3 (1973), 210-219 · Zbl 0283.06003
[6] Dong F. M., Koh K. M., Teo K. L., Chromatic Polynomials and Chromaticity of Graphs, World Scientific, Hackensack, 2005, 384 pp. · Zbl 1070.05038
[7] Farrell E. J., “On chromatic coefficients”, Discrete Math., 29:3 (1980), 257-264 · Zbl 0443.05041
[8] Gein P. A., “About chromatic uniqueness of complete tripartite graph \(K(s,s-1,s-k)\), where \(k\geq 1\) and \(s-k\geq 2\)”, Sib. Èlektron. Mat. Izv., 13 (2016), 331-337 (in Russian) · Zbl 1341.05129
[9] Gein P. A., “About chromatic uniqueness of some complete tripartite graphs”, Sib. Èlektron. Mat. Izv., 14 (2017), 1492-1504 (in Russian) · Zbl 1430.05036
[10] Gein P. A., “On garlands in \(\chi \)-uniquely colorable graphs.”, Sib. Èlektron. Mat. Izv., 16 (2019), 1703-1715 · Zbl 1427.05088
[11] Koh K. M., Teo K. L., “The search for chromatically unique graphs.”, Graphs Combin, 6: 3 (1990), 259-285 · Zbl 0727.05023
[12] Koroleva T. A., “Chromatic uniqueness of some complete tripartite graphs. I”, Trudy Inst. Mat. i Mekh. UrO RAN, 13:3 (2007), 65-83 (in Russian)
[13] Koroleva T. A., “Chromatic uniqueness of some complete tripartite graphs. II”, Izv. Ural. Gos. Univ. Mat. Mekh. Inform., 74 (2010), 39-56 (in Russian) · Zbl 1323.05048
[14] Li N.Ż., Liu R. Y., “The chromaticity of the complete \(t\)-partite graph \(K(1, P_2 \ldots p_t)\)”, J. Xinjiang Univ. Natur. Sci., 7:3 (1990), 95-96 · Zbl 0964.05508
[15] Senchonok T. A., “Chromatic uniqueness of elements of height 2 in lattices of complete multipartite graphs”, Trudy Inst. Mat. i Mekh. UrO RAN, 17:3 (2011), 271-281 (in Russian)
[16] Zhao H., Chromaticity and Adjoint Polynomials of Graphs Zutphen, Wöhrmann Print Service, Netherlands, 2005, 179 pp.
[17] Zhao H., Li X., Zhang Sh., Liu R., “On the minimum real roots of the \(\sigma \)-polynomials and chromatic uniqueness of graphs”, Discrete Math., 281:1-3 (2004), 277-294 · Zbl 1042.05047
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.