Open Mathematics (Dec 2024)
On the existence of tripartite graphs and n-partite graphs
Abstract
A sequence α\alpha of nonnegative integers is said to be graphic if it is the degree sequence of a simple graph GG, and such a graph GG is called a realization of α\alpha . In this article, we generalize Gale and Ryser’s theorem and give the sufficient condition and necessary condition for a triple to be realized by a tripartite graph. Not only that, we also give another stronger monotonous degree condition.
Keywords