Several Studies on Complete t-Partite Graphs

Abstract

Abstract: The article presents several achievements, problems, and conjectures in the study of complete t-partite graphs from seven
perspectives: (1) the counting formulas of S(n)-factors; (2) the counting formulas of the partitions of stable sets; (3) chromatic polynomials and unimodality; (4) mean color numbers; (5) independence numbers and independence polynomials; (6) the Hosoya index and the Merrifield-Simmons index; (7) the chromatic uniqueness. These findings enrich the intersection of extremal graph theory and algebraic graph theory.

Key words: S(n)-factor, stable set, chromatic polynomial, mean color number, independence polynomial

CLC Number:

Yang Huang, Yang Zhongyan, Yang Limin. Several Studies on Complete t-Partite Graphs[J]. Journal of Dali University, 2026, 11(6): 11-18.

References

〔1〕杨利民，王天明，年四洪. N [(X1,X2,...,Xi ),k ]的计数公式〔J〕. 大连理工大学学报， 2007， 47（6）：925-930.
〔2〕 YANG L M， WANG T M. The Represnteing Formula of N（G，k）〔J〕. Journal of Combinatorics， Graph Theory and Applications，2026， 1（1）：60-80.
〔3〕 YANG L M， NIAN S H. The Unimodality of N（G，k） and a Combinatorial Identity on Two Kinds Stirling Numbers〔J〕. Far East Journal of Applied Mathematics， 2006， 24（1）：119-128.
〔4〕 YANG L M. Enumeration of Independent Sets of Graphs〔J〕. International Journal of Combinatorial Graph Theory and Applica⁃
tions， 2021， 6（1）：61-69.
〔5〕杨利民，王天明. 色多项式的显示公式〔J〕. 数学进展， 2006， 35（1）：55-66.
〔6〕杨利民，杨娇艳. 稳定集合分拆的伴随多项式和单峰性〔J〕. 大理大学学报， 2024， 9（12）: 1-11.
〔7〕 COMTET L. Advanced Combinatorics: The Art of Finite and Infinite Expansions〔M〕. Dordrecht： Springer Netherlands， 1974.

〔8〕 BONDY J A， MURTY U S R. Graph Theory with Applications〔M〕. London： Macmillan， 1976.

〔9〕 HUH J. Milnor Numbers of Projective Hypersurfaces and the Chromatic Polynomial of Graphs〔J〕. Journal of the American Mathematical Society， 2012， 25（3）： 907-927.
〔10〕杨利民. 理想子图计数及其应用〔J〕. 大连理工大学学报， 1989， 29（5）： 605-609.
〔11〕 YANG L M， WANG T M. The Number of Independent Sets of Windgraphs and the Formula Convolutions of N (-G ,k)〔J〕. Far
East Journal of Mathematical Sciences， 2004， 15（3）：393-404.
〔12〕 YANG L M， NIAN S H. The Number of k Independent Sets of Graphs and the Mean Color Numbers of Graphs〔J〕. International Journal of Combinatorial Graph Theory and Applications， 2021， 6（1）：17-29.
〔13〕杨利民. 图的完全积的独立数和独立多项式〔J〕. 大理大学学报， 2023， 8（6）： 1-8.
〔14〕 LEVIT V E， MANDRESCU E. Independence Polynomials of Well-Covered Graphs： Generic Counterexamples for the Unimodality Conjecture〔J〕. European Journal of Combinatorics， 2006， 27（6）： 931-939.
〔15〕杨利民，段丽燕，王天明. 四叶树Hosoya指标显式公式及其序列〔J〕. 大连理工大学学报， 2016， 56（6）： 657-661.
〔16〕 HUANG Y H. Hoaoya Index and the Matching Defect Polynomials of a graph G without K3 Subgraph〔J〕. Journal of Combinatorics，Graph Theory and Applications， 2026， 1（1）：36-50.
〔17〕徐利民. 关于完全t 部图的色唯一性〔J〕. 运筹与管理， 2007， 16（4）： 61-63.
〔18〕 KOH K M， TEO K L. The Search for Chromatically Unique Graphs〔J〕. Graphs and Combinatorics， 1990， 6（3）： 259-285.
〔19〕 ZHAO H X， LI X L， LIU R Y， et al. The Chromaticity of Certain Complete Multipartite Graphs〔J〕. Graphs and Combinatorics，2004， 20（3）： 423-434.
〔20〕 DURON J， ESPERET L， RAYMOND J F. Long Induced Paths and Forbidden Patterns： Polylogarithmic Bounds〔J〕. SIAM Journal on Discrete Mathematics， 2026， 40（1）： 52-81.

[1]	Yang Limin, Yang Jiaoyan. Adjoint Polynomials and Unimodality of Stable Set Partitons [J]. Journal of Dali University, 2024, 9(12): 1-11.
[2]	Yang Limin. Independent Number and Independent Polynomial of Complete Product of Graph [J]. Journal of Dali University, 2023, 8(6): 1-8.