×

About chromatic uniqueness of some complete tripartite graphs. (Russian. English summary) Zbl 1430.05036

Summary: Let \(P(G, x)\) be the chromatic polynomial of a graph \(G\). A graph \(G\) is called chromatically unique if for any graph \(H,P(G,x) = P(H, x)\) implies that \(G\) and \(H\) are isomorphic. In this paper we show that full tripartite graph \(K(n_1, n_2, n_3)\) is chromatically unique if \(n_1\geq n_2\geq n_2\geq n_3, n_1- n_3\leq 5\) and \(n_1+n_2+n_3\not\equiv 2 \mod 3\).

MSC:

05C15 Coloring of graphs and hypergraphs
05C31 Graph polynomials
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] M.O. Asanov, V.A. Baranskii, V.V. Rasin,Discrete Mathematics: Graphs, Matroids, Algorithms, Publ. Lan’, 2010. [In Russian] ISBN 978-5-8114-1068-2
[2] F.M. Dong, K.M. Koh, K.L. Teo,Chromatic polynomials and chromaticity of graphs, World Scientific, Hackensack, NJ, 2005. MR2159409 · Zbl 1070.05038
[3] H. Zhao,Chromaticity and adjoint polynomials of graphs. W¨ohrmann Print Service, Zutphen, The Netherlands, 2005. MR2715784
[4] K.M. Koh, K.L. Teo,The search for chromatically unique graphs, Graphs Combin.,6:3, 1990, 259-285. MR1081201 · Zbl 0727.05023
[5] V.A. Baranskii, T.A. Koroleva,Chromatic uniqueness of certain complete tripartite graphs, Izv. Ural. Gos. Univ. Mat. Mekh. Inform.,74:12 (2010), 5-26. [Russian. English summary] MR2906104 · Zbl 1323.05044
[6] T.A. Koroleva,Chromatic uniqueness of some complete tripartite graphs. I, Trudy Inst. Mat. i Mekh. UrO RAN,13:3 (2007), 65-83. [In Russian] http://mi.mathnet.ru/eng/timm108
[7] T.A. Koroleva,Chromatic uniqueness of some complete tripartite graphs. II, Izv. Ural. Gos. Univ. Mat. Mekh. Inform.,74:2010, 39-56. [Russian. English summary] MR2906106 · Zbl 1323.05048
[8] V.A. Baranskii , T.A. Sen’chonok,Chromatic uniqueness of elements of height≤3in lattices of complete multipartite graphs, Proceedings of the Steklov Institute of Mathematics,279:S.1 (2012), 1-16 (translation from Tr. Inst. Mat. Mekh. (Ekaterinburg),17:4(2011), 3-18). Zbl 1301.05117 · Zbl 1301.05117
[9] R. Liu, H. Zhao, Ch. Ye,A complete solution to a conjecture on chromatic uniqueness of complete tripartite graphs, Discrete Math.,289:1-3 (2004), 175-179. MR2106041 · Zbl 1061.05034
[10] P.A. Gein,About chromatic uniqueness of complete tripartite graph𝐾(𝑠, 𝑠−1, 𝑠−𝑘), where 𝑘≥1and𝑠−𝑘≥2, Sib. ‘Elektron. Mat. Izv.,13(2016), 331-337. [Russian, English abstract] MR3506896 · Zbl 1341.05129
[11] T. Brylawski,The lattice of integer partitions, Dicrete Math.,6(1973), 210-219. MR0325405 · Zbl 0283.06003
[12] V.A. Baranskii, T.A. Koroleva, T.A. Senchonok,On the partition lattice of all integers, Sib. Elektron. Mat. Izv.,‘13(2016), 744-753. [Russian, English abstract] MR3553165 · Zbl 1370.05014
[13] H. Zhao, X. Li, Sh. Zhang, R. Liu,On the minimum real roots of the𝜎-polynomials and chromatic uniqueness of graphs, Discrete Mathematics,281:1-3 (2004), 277-294. MR2047774 · Zbl 1042.05047
[14] E.J. Farrell,On chromatic coefficients, Discrete Math.,29:3 (1980), 257-264. MR0560769 · Zbl 0443.05041
[15] V.A. Baranskii, S.V. Viharev,On the chromatic invariants of bipartite graphs, Izv. Ural. Gos. Univ., Mat. Mekh.,36:7 (2005), 25-34. [Russian. English summary] Zbl 1189.05057 · Zbl 1189.05057
[16] G.
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.