Robertson's Hadwiger-type conjecture for degree sequences

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.

Sources & referencesView supporting material

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.