Improved bound for the dimension of posets of treewidth two

DOI10.1016/J.DISC.2019.111605MaRDI QIDQ2279268zbMATH OpenOpenAlexWikidataFDO

Authors Michał T. Seweryn

Publication date 12 December 2019

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1902.01189

zbMATH Keywords

order dimensionseries-parallel graphstreewidth

Mathematics Subject Classification ID

Distance in graphs (05C12) Partial orders, general (06A06) Combinatorics of partially ordered sets (06A07)

Abstract: Joret et al. proved that posets with cover graphs of treewidth at most 2 have dimension at most 1276. Their proof is long and very complex. We give a short and much simpler proof that the dimension of such posets is at most 12.

Recommendations

• On the dimension of posets with cover graphs of treewidth 2
• The dimension of posets with planar cover graphs.
• Posets with cover graph of pathwidth two have bounded dimension
• Dimension of posets with planar cover graphs excluding two long incomparable chains
• Tree-width and dimension

Cites work

• Graph Classes: A Survey
• On the dimension of partially ordered sets
• On the dimension of posets with cover graphs of treewidth 2
• Posets with cover graph of pathwidth two have bounded dimension
• The dimension of planar posets
• The dimension of posets with planar cover graphs.
• Topological minors of cover graphs and dimension

Cited in

(9)

• On some complexity properties of N-free posets and posets with bounded decomposition diameter
• Improved bounds for the number of forests and acyclic orientations in the square lattice
• Excluding a ladder
• Local dimension is unbounded for planar posets
• On the dimension of posets with cover graphs of treewidth 2
• Boolean dimension and tree-width
• Posets with cover graph of pathwidth two have bounded dimension
• Cliquewidth and dimension
• Forcing the wheel

This page was built for publication: Improved bound for the dimension of posets of treewidth two

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2279268)