A semigroup proof of the bounded degree case of SB Rao's Conjecture on degree sequences and a bipartite analogue

作者：Altomare Christian Joseph^*

来源：Journal of Combinatorial Theory - Series B, 2012, 102(3): 756-759.

DOI：10.1016/j.jctb.2011.09.002

• Rao's Conjecture
• Semigroup lemma
• Degree sequence
• Grounded
• Bipartite
• Bounded

S.B. Rao conjectured in 1980 that graphic degree sequences are well quasi ordered by a relation <= defined in terms of the induced subgraph relation (Rao, 1981 [7]). In 2008, M. Chudnovsky and P. Seymour proved this longstanding conjecture by giving structure theorems for graphic degree sequences (Chudnovsky and Seymour, in preparation [2].
In this paper, we prove and use a semigroup lemma to give a short proof of the bounded degree case of Rao's Conjecture that is independent of the Chudnovsky-Seymour structure theory. In fact, we affirmatively answer two questions of N. Robertson (2006) [8], the first of which implies the bounded degree case of Rao's Conjecture.

• 出版日期2012-5