Posets with cover graph of pathwidth two have bounded dimension

The dimension of an ordered set \(P\) with order relation \(\leq \) is the smallest number of total orders whose intersection is the order \(\leq \). Let \(G=(V,E)\) be a graph, let \(T\) be a tree and let \({\mathcal V} =(V_t )_{t\in T}\) be a family of subsets \(V_t \subseteq V\) indexed by the tree \(T\). Then \((T,{\mathcal V}) \) is called a tree-decomposition of \(G\) iff \(V=\bigcup _{t\in T} V_t \), every edge of \(G\) is a subset of a set \(V_t \), and, if \(t_1\), \(t_2\), \(t_3 \) are vertices of \(T\) such that \(t_2 \) lies on the unique path from \(t_1 \) to \(t_3 \) in \(T\), then \(V_{t_1 } \cap V_{t_3} \subseteq V_{t_2} \). The width of a tree decomposition is \(\max _{t\in T} |V_t |-1\). The treewidth \(\mathrm{tw}(G)\) is the smallest width of a tree-decomposition of \(G\). A path-decomposition is a tree-decomposition in which \(T\) is a path and the pathwidth of a graph is the smallest width of a path-decomposition of \(G\). It has been long known that, if \(P\) is a connected ordered set whose cover graph has treewidth \(1\) (that is, it is a tree), then its dimension is at most \(3\). Moreover, there are ordered sets of arbitrarily high dimension whose cover graph has pathwidth \(3\), which leaves path- and treewidth \(2\) as the last cases to consider. The authors show that the dimension of an ordered set whose cover graph has pathwidth at most \(2\) is at most \(17\). They also note that the cover graph of any ordered set that contains the standard example \(S_5 \) has treewidth at least \(3\) and that it has been proved in [\textit{G. Joret} et al., ``On the dimension of posets with cover graphs of treewidth 2, Order (to appear), \url{doi:10.1007/s11083-016-9395-y}] that the dimension of an ordered set whose cover graph has treewidth at most \(2\) is at most \(1276\).

Recommendations

Cites work

Cited in

(15)

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)