Posets with cover graph of pathwidth two have bounded dimension (Q304175): Difference between revisions
From MaRDI portal
Created a new Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(7 intermediate revisions by 5 users not shown) | |||
Property / review text | |||
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\). | |||
Property / review text: 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\). / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 06A07 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 05C25 / rank | |||
Normal rank | |||
Property / zbMATH DE Number | |||
Property / zbMATH DE Number: 6619132 / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
poset | |||
Property / zbMATH Keywords: poset / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
pathwidth | |||
Property / zbMATH Keywords: pathwidth / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
cover graph | |||
Property / zbMATH Keywords: cover graph / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
dimension | |||
Property / zbMATH Keywords: dimension / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
treewidth | |||
Property / zbMATH Keywords: treewidth / rank | |||
Normal rank | |||
Property / reviewed by | |||
Property / reviewed by: Bernd S. W. Schröder / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W3098298570 / rank | |||
Normal rank | |||
Property / arXiv ID | |||
Property / arXiv ID: 1308.4877 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On the structure of graphs with path-width at most two / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3577833 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Adjacency posets of planar graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The dimension of posets with planar cover graphs. / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: S-functions for graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Tree-width and dimension / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On the dimension of posets with cover graphs of treewidth 2 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On the dimension of partially ordered sets / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Obstruction set isolation for the gate matrix layout problem / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Graph minors. III. Planar tree-width / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Graph minors. XX: Wagner's conjecture / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Edge subdivision and dimension / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Dimension and height for posets with planar cover graphs. / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4004146 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The dimension of planar posets / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 11:57, 12 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Posets with cover graph of pathwidth two have bounded dimension |
scientific article |
Statements
Posets with cover graph of pathwidth two have bounded dimension (English)
0 references
24 August 2016
0 references
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\).
0 references
poset
0 references
pathwidth
0 references
cover graph
0 references
dimension
0 references
treewidth
0 references