Robertson's Hadwiger-type conjecture for degree sequences
Robertson's Hadwiger-type conjecture for degree sequences
Let be a graphic degree sequence, and let be the set of its simple graph realizations. Define as the maximum chromatic number over graphs in , and define as the maximum order of a clique minor over graphs in . Robertson's conjecture. For every graphic degree sequence ,
This is a relaxation of Hadwiger's conjecture, which asks whether every graph of chromatic number contains a -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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.