S. B. Rao's well-quasi-ordering conjecture for degree sequences

About 17 years old · traced to

Let a graphic degree sequence be a multiset of non-negative integers realized as the degree sequence of a simple graph. For a degree sequence DD, let

R(D)={G∣D(G)=D}\mathcal{R}(D)=\{G\mid D(G)=D\}

be its set of realizations. Define D⪯D′D\preceq D' if there exist G∈R(D)G\in\mathcal{R}(D) and G′∈R(D′)G'\in\mathcal{R}(D') such that GG is an induced subgraph of G′G'. Rao's conjecture. The degree sequences are well-quasi-ordered with respect to the relation ⪯\preceq. Chudnovsky and Seymour announced a proof of this conjecture, so the claim is no longer open.

References

Primary source

Zdenek Dvorak and Bojan Mohar, “Chromatic number and complete graph substructures for degree sequences”, arXiv:0907.1583 (2009).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.