Robertson's Hadwiger-type conjecture for degree sequences

About 17 years old · traced to

Let DD be a graphic degree sequence, and let R(D)\mathcal{R}(D) be the set of its simple graph realizations. Define χ(D)\chi(D) as the maximum chromatic number over graphs in R(D)\mathcal{R}(D), and define H(D)H(D) as the maximum order of a clique minor over graphs in R(D)\mathcal{R}(D). Robertson's conjecture. For every graphic degree sequence DD,

χ(D)≤H(D).\chi(D)\le H(D).

This is a relaxation of Hadwiger's conjecture, which asks whether every graph of chromatic number kk contains a kk-clique minor. The source states that Hadwiger's conjecture remains open, while this degree-sequence relaxation is presented as a conjecture; the paper's abstract says that it is settled, but the supplied candidate does not specify the proof status of this particular claim.

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.