Rao's degree sequence conjecture

Research output: Contribution to journalArticlepeer-review

5 Scopus citations

Abstract

Let us say two (simple) graphs G, G' are degree-equivalent if they have the same vertex set, and for every vertex, its degrees in G and in G' are equal. In the early 1980's, S.B. Rao made the conjecture that in any infinite set of graphs, there exist two of them, say G and H, such that H is isomorphic to an induced subgraph of some graph that is degree-equivalent to G. We prove this conjecture.

Original languageEnglish (US)
Pages (from-to)44-92
Number of pages49
JournalJournal of Combinatorial Theory. Series B
Volume105
Issue number1
DOIs
StatePublished - 2014

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics

Keywords

  • Graph structure theory
  • Induced subgraph
  • Well-quasi-ordering

Fingerprint Dive into the research topics of 'Rao's degree sequence conjecture'. Together they form a unique fingerprint.

Cite this