A semigroup proof of the bounded degree case of S.B. Rao's conjecture on degree sequences and a bipartite analogue
From MaRDI portal
Publication:414650
DOI10.1016/J.JCTB.2011.09.002zbMATH Open1241.05020arXiv1010.5481OpenAlexW2090272461MaRDI QIDQ414650FDOQ414650
Authors: Christian Altomare 
Publication date: 11 May 2012
Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)
Abstract: 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.
Full work available at URL: https://arxiv.org/abs/1010.5481
Recommendations
- Two short proofs of the bounded case of S. B. Rao's degree sequence conjecture
- Convergence results for a class of spectrally hyperviscous models of 3-D turbulent flow
- Rao's degree sequence conjecture
- A short constructive proof of A.R. Rao's characterization of potentially \(K_{r+1}\)-graphic sequences
- A simple criterion on degree sequences of graphs
Cites Work
Cited In (4)
This page was built for publication: A semigroup proof of the bounded degree case of S.B. Rao's conjecture on degree sequences and a bipartite analogue
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q414650)
