Nordhaus–Gaddum product lower-bound conjecture for the Hadwiger number

Let G1,,GrG_1,\ldots,G_r be graphs on a common vertex set of size nn, whose edge sets partition the edges of KnK_n, and let \ngplη(r;n)\ngpl{\eta}(r;n) denote the minimum of i=1rη(Gi)\prod_{i=1}^r\eta(G_i) over all such rr-decompositions, where η(G)\eta(G) is the Hadwiger number of GG. Product lower-bound conjecture. For all r2r\geq 2 and n1n\geq 1,

\ngplη(r;n)=n.\ngpl{\eta}(r;n)=n.

The source notes that this conjecture is implied by Hadwiger's conjecture. The paper proves only the bounds (0.513)r2n\ngplη(r;n)n(0.513)^{r-2}n\leq\ngpl{\eta}(r;n)\leq n.

Sources & referencesView supporting material

Primary source

Leslie Hogben, Jephian C. -H. Lin and Michael Young, “Multi-part Nordhaus-Gaddum type problems for tree-width, Colin de Verdière type parameters, and Hadwiger number”, arXiv:1604.08817 (2016).

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.