ON CHROMATIC UNIQUENESS OF SOME COMPLETE TRIPARTITE GRAPHS

Pavel A. Gein     (Ural Federal University, 51, Lenin ave., Ekaterinburg, 620000, Russian Federation)

Abstract


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\).


Keywords


Chromatic uniqueness, Chromatic equivalence, Complete multipartite graphs, Chromatic polynomial

Full Text:

PDF

References


  1. Asanov M.O., Baransky V.A., Rasin V.V. Diskretnaya matematika: grafy, matroidy, algoritmy [Discrete Mathematics: Graphs, Matroids, Algorithms]. Saint-Petersburg: “Lan”, 2010. 364 p. (in Russian)
  2. Baransky V.A., Koroleva T.A. Chromatic uniqueness of certain complete tripartite graphs. Izv. Ural. Gos. Univ. Mat. Mekh. Inform., 2010. Vol. 74, No. 12. P. 5–26. (in Russian)
  3. Baransky V.A., Koroleva T.A., Senchonok T.A. On the partition lattice of all integers. Sib. Èlektron. Mat. Izv., 2016. Vol. 13. P. 744–753. DOI: 10.17377/semi.2016.13.060 (in Russian)
  4. Baranskii V.A., Sen’chonok T.A. Chromatic uniqueness of elements of height ≤ 3 in lattices of complete multipartite graphs. Proc. Steklov Inst. Math., 2012. Vol. 279. P. 1–16. DOI: 10.1134/S0081543812090015
  5. Brylawski T. The lattice of integer partitions. Discrete Math., 1973. Vol. 6, No. 3. P. 210–219. DOI: 10.1016/0012-365X(73)90094-0
  6. Dong F.M., Koh K.M., Teo K.L. Chromatic Polynomials and Chromaticity of Graphs. Hackensack: World Scientific, 2005. 384 p. DOI: 10.1142/5814
  7. Farrell E.J. On chromatic coefficients. Discrete Math., 1980. Vol. 29, No. 3. P. 257–264. DOI: 10.1016/0012-365X(80)90154-5
  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., 2016. Vol. 13. P. 331–337. DOI: 10.17377/semi.2016.13.027 (in Russian)
  9. Gein P.A. About chromatic uniqueness of some complete tripartite graphs. Sib. Èlektron. Mat. Izv., 2017. Vol. 14. P. 1492–1504. DOI: 10.17377/semi.2017.14.129 (in Russian)
  10. Gein P.A. On garlands in χ-uniquely colorable graphs. Sib. Èlektron. Mat. Izv., 2019. Vol. 16. P. 1703–1715. DOI: 10.33048/semi.2019.16.120
  11. Koh K.M., Teo K.L. The search for chromatically unique graphs. Graphs Combin., 1990. Vol. 6, No. 3. P. 259–285. DOI: 10.1007/BF01787578
  12. Koroleva T.A. Chromatic uniqueness of some complete tripartite graphs. I. Trudy Inst. Mat. i Mekh. UrO RAN, 2007. Vol. 13, No. 3. P. 65–83. (in Russian)
  13. Koroleva T.A. Chromatic uniqueness of some complete tripartite graphs. II. Izv. Ural. Gos. Univ. Mat. Mekh. Inform., 2010. Vol. 74. P. 39–56. (in Russian)
  14. Li N.Z., Liu R.Y. The chromaticity of the complete \(t\)-partite graph \(K(1, P_2 \ldots p_t)\). J. Xinjiang Univ. Natur. Sci., 1990. Vol. 7, No. 3. P. 95–96.
  15. Senchonok T.A. Chromatic uniqueness of elements of height 2 in lattices of complete multipartite graphs. Trudy Inst. Mat. i Mekh. UrO RAN, 2011. Vol. 17, No. 3. P. 271–281. (in Russian)
  16. Zhao H. Chromaticity and Adjoint Polynomials of Graphs. Zutphen, Netherlands: Wöhrmann Print Service, 2005. 179 p.
  17. Zhao H., Li X., Zhang Sh., Liu R. On the minimum real roots of the σ-polynomials and chromatic uniqueness of graphs. Discrete Math., 2004. Vol. 281, No. 1–3. P. 277–294. DOI: 10.1016/j.disc.2003.06.010




DOI: http://dx.doi.org/10.15826/umj.2021.1.004

Article Metrics

Metrics Loading ...

Refbacks

  • There are currently no refbacks.