A semigroup proof of the bounded degree case of S.B. Rao始s Conjecture on degree sequences and a bipartite analogue

详细信息	查看全文 | 推荐本文 |

• 作者：Christian Joseph Altomare ^{altomare@math.ohio-state.edu}
• 关键词：Rao始s Conjecture ; Semigroup lemma ; Degree sequence ; Grounded ; Bipartite ; Bounded
• 刊名：Journal of Combinatorial Theory ; Series B
• 出版年：2012
• 期刊代码：135_00958956
• 类别：cp
• 出版时间：May, 2012
• 卷：102
• 期：3
• 页码：756-759
• 文件大小：115 K

摘要

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 ). In 2008, M. Chudnovsky and P. Seymour proved this longstanding conjecture by giving structure theorems for graphic degree sequences (Chudnovsky and Seymour, in preparation ).

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) , the first of which implies the bounded degree case of Rao始s Conjecture.