Posets with cover graph of pathwidth two have bounded dimension

DOI10.1007/S11083-015-9359-7zbMATH Open1364.06002arXiv1308.4877OpenAlexW3098298570MaRDI QIDQ304175FDOQ304175

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

Publication date: 24 August 2016

Published in: Order (Search for Journal in Brave)

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

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

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

zbMATH Keywords

treewidthpathwidthdimensionposetcover graph

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (14)

• 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
• Directed tree decompositions
• Tree-width and dimension
• 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
• Dimension and cut vertices: an application of Ramsey theory

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)