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

• tripartite graphs
• monotonous degree condition
• n-partite graphs
• 05c07