Characterization conjecture for unavoidable graphs in poset cover graphs
Characterization conjecture for unavoidable graphs in poset cover graphs
Let be a graph. Call unavoidable if the cover graph of every poset of sufficiently large dimension contains as a minor. Kelly's construction refers to the family of planar cover graphs of pathwidth arising from Kelly's examples of posets with unbounded dimension. Characterization conjecture for unavoidable graphs. A graph is unavoidable if and only if is a minor of some graph from Kelly's construction. Ladders and are known to be unavoidable, while the source describes a full characterization as open and presents Kelly's construction as a necessary restriction.
Sources & referencesView supporting material
Primary source
Tony Huynh, Gwenaël Joret, Piotr Micek, Michał T. Seweryn and Paul Wollan, “Excluding a ladder”, arXiv:2002.00496 (2021).
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.