The minor-excluded-cover-graph dim-boundedness conjecture

About 1 year old · traced to

Let KtK_t denote the complete graph on tt vertices, and let a graph exclude KtK_t as a minor if it has no graph minor isomorphic to KtK_t. The dimension of a poset PP, denoted dim⁡(P)\dim(P), is the least number of linear extensions whose intersection is PP. A class of posets is dim-bounded if the dimensions of its members are bounded by a function of the indicated graph parameter. The minor-excluded-cover-graph conjecture. For every positive integer tt, the class of posets with cover graphs excluding KtK_t as a minor is dim-bounded. This statement is presented as a conjectural generalization of the planar cover-graph and bounded-treewidth results described in the paper. The supplied text gives supporting context but no resolution of the conjecture.

References

Primary source

Heather Smith Blake, Jędrzej Hodor, Piotr Micek, Michał T. Seweryn and William T. Trotter, “Planarity and dimension I”, arXiv:2510.18603 (2025).

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.