Rao's degree sequence conjecture

Maria Chudnovsky; Paul Seymour

doi:10.1016/j.jctb.2013.12.003

Rao's degree sequence conjecture

Maria Chudnovsky, Paul Seymour

Mathematics

Research output: Contribution to journal › Article › peer-review

7 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 language	English (US)
Pages (from-to)	44-92
Number of pages	49
Journal	Journal of Combinatorial Theory. Series B
Volume	105
Issue number	1
DOIs	https://doi.org/10.1016/j.jctb.2013.12.003
State	Published - 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

Access to Document

10.1016/j.jctb.2013.12.003

Cite this

@article{9c65b69e768741f4b7bd68cd67484bb3,

title = "Rao's degree sequence conjecture",

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.",

keywords = "Graph structure theory, Induced subgraph, Well-quasi-ordering",

author = "Maria Chudnovsky and Paul Seymour",

year = "2014",

doi = "10.1016/j.jctb.2013.12.003",

language = "English (US)",

volume = "105",

pages = "44--92",

journal = "Journal of Combinatorial Theory. Series B",

issn = "0095-8956",

publisher = "Academic Press Inc.",

number = "1",

}

TY - JOUR

T1 - Rao's degree sequence conjecture

AU - Chudnovsky, Maria

AU - Seymour, Paul

PY - 2014

Y1 - 2014

N2 - 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.

AB - 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.

KW - Graph structure theory

KW - Induced subgraph

KW - Well-quasi-ordering

UR - http://www.scopus.com/inward/record.url?scp=84894868998&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84894868998&partnerID=8YFLogxK

U2 - 10.1016/j.jctb.2013.12.003

DO - 10.1016/j.jctb.2013.12.003

M3 - Article

AN - SCOPUS:84894868998

SN - 0095-8956

VL - 105

SP - 44

EP - 92

JO - Journal of Combinatorial Theory. Series B

JF - Journal of Combinatorial Theory. Series B

IS - 1

ER -

Rao's degree sequence conjecture

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this