Chromatic uniqueness of elements of height 2 in lattices of complete multipartite graphs

T. A. Senchonok

Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 17 (2011) no. 3, pp. 271-281

Résumé

The purpose of the paper is to prove the following theorem. Let integers $n,t$, and $h$ be such that $0$ and $h\leq2$. Then, any complete $t$-partite graph with nontrivial parts that has height $h$ in the lattice $NPL(n,t)$ is chromatically unique.

Détail

Mots-clés : integer partition, complete multipartite graph
Keywords: lattice, graph, chromatic polynomial, chromatic uniqueness.

Bibliographie

[1] Endryus G., Teoriya razbienii, Nauka, M., 1982, 256 pp. | MR

[2] Baranskii V. A., Koroleva T. A., “Reshetka razbienii naturalnogo chisla”, Dokl. RAN, 418:4 (2008), 439–442 | MR

[3] Asanov M. O., Baranskii V. A., Rasin V. V., Diskretnaya matematika: grafy, matroidy, algoritmy, “Lan”, SPb., 2010, 368 pp.

[4] Read R. C., “An introduction to chromatic polynomials”, J. Comb. Theory, 4 (1968), 52–71 | DOI | MR

[5] Chao C. Y., Whitehead E. G. (Jr.), “On chromatic equivalence of graphs”, Theory and Appl. of Graphs, Lecture Notes in Math., 642, Springer, Berlin, 1978, 121–131 | MR

[6] Zhao H., Chromaticity and adjoint polynomials of graphs, Whrmann Print Service, Zutphen, 2005, 169 pp. | MR

[7] Chao C. Y., Novacky G. A. (Jr.), “On maximally saturated graphs”, Discr. Math., 41:2 (1982), 139–143 | DOI | MR | Zbl

[8] Baranskii V. A., Koroleva T. A., “Khromaticheskaya opredelyaemost atomov v reshetkakh polnykh mnogodolnykh grafov”, Trudy Instituta matematiki i mekhaniki UrO RAN, 13, no. 3, 2007, 22–29

[9] Koroleva T. A., “Khromaticheskaya opredelyaemost nekotorykh polnykh trekhdolnykh grafov. I”, Trudy Instituta matematiki i mekhaniki UrO RAN, 13, no. 3, 2007, 65–83

[10] Koroleva T. A., “Khromaticheskaya opredelyaemost nekotorykh polnykh trekhdolnykh grafov. II”, Izv. Ural. gos. un-ta. Matematika, mekhanika i informatika, 2010, no. 74(12), 39–56

[11] Baranskii V. A., Koroleva T. A., “Khromaticheskaya opredelyaemost nekotorykh polnykh trekhdolnykh grafov”, Izv. Ural. gos. un-ta. Matematika, mekhanika i informatika, 2010, no. 74(12), 5–26

[12] Koh K. M., Teo K. L., “The search for chromatically unique graphs”, Graphs Combin., 6 (1990), 259–285 | DOI | MR | Zbl

[13] Farrell E. J., “On chromatic coefficients”, Discr. Math., 29:3 (1980), 257–264 | DOI | MR | Zbl

[14] Baranskii V. A., Vikharev S. V., “O khromaticheskikh invariantakh dvudolnykh grafov”, Izv. Ural. gos. un-ta. Matematika i mekhanika, 2005, no. 36(7), 25–34 | MR

[15] Senchonok T. A., Baranskii V. A., “Klassifikatsiya elementov maloi vysoty v reshetkakh polnykh mnogodolnykh grafov”, Trudy Instituta matematiki i mekhaniki UrO RAN, 17, no. 2, 2011, 159–173