Posets with cover graph of pathwidth two have bounded dimension
Preprint
Abstract
Joret, Micek, Milans, Trotter, Walczak, and Wang recently asked if there exists a constant $d$ such that if $P$ is a poset with cover graph of $P$ of pathwidth at most $2$, then $\dim(P)\leq d$. We answer this question in the affirmative by showing that $d=17$ is sufficient. We also show that if $P$ is a poset containing the standard example $S_5$ as a subposet, then the cover graph of $P$ has treewidth at least $3$.
Keywords
All Related Versions
This publication has 12 references indexed in Scilit:
- On the Dimension of Posets with Cover Graphs of Treewidth 2Order, 2016
- Tree-width and dimensionCombinatorica, 2015
- The Dimension of Posets with Planar Cover GraphsGraphs and Combinatorics, 2014
- Dimension and height for posets with planar cover graphsEuropean Journal of Combinatorics, 2014
- Adjacency posets of planar graphsDiscrete Mathematics, 2010
- Obstruction set isolation for the gate matrix layout problemDiscrete Applied Mathematics, 1994
- Edge subdivision and dimensionOrder, 1988
- Graph minors. III. Planar tree-widthJournal of Combinatorial Theory, Series B, 1984
- On the dimension of partially ordered setsDiscrete Mathematics, 1981
- S-functions for graphsJournal of Geometry, 1976