A Semigroup Proof of the Bounded Degree Case of S.B. Rao's Conjecture on Degree Sequences and a Bipartite Analogue

Details A Semigroup Proof of the Bounded Degree Case of S.B. Rao's Conjecture on Degree Sequences and a Bipartite Analogue A Semigroup Proof of the Bounded Degree Case of S.B. Rao's Conjecture on Degree Sequences and a Bipartite Analogue

2010-10-26

arxiv.org/abs/1010.5481v1

Mathematics

Combinatorics

10 pages

Scientific paper

S.B. Rao conjectured in 1971 that graphic degree sequences are well quasi ordered by a relation defined in terms of the induced subgraph relation. In 2008, M. Chudnovsky and P. Seymour proved this long standing Rao's Conjecture by giving structure theorems for graphic degree sequences. In this paper, we prove and use a variant of Dickson's Lemma from commutative semigroup theory 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, the first of which implies the bounded degree case of Rao's Conjecture.

Affiliated with

Also associated with

No associations

Rating

A Semigroup Proof of the Bounded Degree Case of S.B. Rao's Conjecture on Degree Sequences and a Bipartite Analogue does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A Semigroup Proof of the Bounded Degree Case of S.B. Rao's Conjecture on Degree Sequences and a Bipartite Analogue, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Semigroup Proof of the Bounded Degree Case of S.B. Rao's Conjecture on Degree Sequences and a Bipartite Analogue will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-160059