Posets with cover graph of pathwidth two have bounded dimension

DOI10.1007/S11083-015-9359-7MaRDI QIDQ304175zbMATH OpenOpenAlexFDO

Authors Csaba Biró, Mitchel T. Keller, Stephen J. Young

Publication date 24 August 2016

Published in Order (Search for Journal in Brave)

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

zbMATH Keywords

treewidthpathwidthdimensionposetcover graph

Mathematics Subject Classification ID

Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Combinatorics of partially ordered sets (06A07)

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)leqd$. 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$.

Recommendations

• On the dimension of posets with cover graphs of treewidth 2
• Tree-width and dimension
• Comparing Dushnik-Miller dimension, Boolean dimension and local dimension
• Boolean dimension and tree-width
• Improved bound for the dimension of posets of treewidth two

Cites work

• scientific article; zbMATH DE number 53952 (Why is no real title available?)
• Adjacency posets of planar graphs
• Dimension and height for posets with planar cover graphs.
• Edge subdivision and dimension
• Graph minors. III. Planar tree-width
• Graph minors. XX: Wagner's conjecture
• Graph theory
• Obstruction set isolation for the gate matrix layout problem
• On the dimension of partially ordered sets
• On the dimension of posets with cover graphs of treewidth 2
• On the structure of graphs with path-width at most two
• S-functions for graphs
• The dimension of planar posets
• The dimension of posets with planar cover graphs.
• Tree-width and dimension

Cited in

(14)

• Dimension and cut vertices: an application of Ramsey theory
• On the geometric Ramsey number of outerplanar graphs
• Improved bound for the dimension of posets of treewidth two
• Planar posets, dimension, breadth and the number of minimal elements
• Word-representable graphs: orientations, posets, and bounds
• Minors and dimension
• Trees and circle orders
• Boolean dimension and tree-width
• Tree-width and dimension
• Directed tree decompositions
• On the dimension of posets with cover graphs of treewidth 2
• Boolean dimension and local dimension
• Dimension of posets with planar cover graphs excluding two long incomparable chains
• WEAK DIMENSION AND CHAIN-WEAK DIMENSION OF ORDERED SETS

This page was built for publication: Posets with cover graph of pathwidth two have bounded dimension

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