Simple view
Full metadata view
Authors
Statistics
On the dimension of posets with cover graphs of treewidth 2
poset
dimension
treewidth
In 1977, Trotter and Moore proved that a poset has dimension at most 3 whenever its cover graph is a forest, or equivalently, has treewidth at most 1. On the other hand, a well-known construction of Kelly shows that there are posets of arbitrarily large dimension whose cover graphs have treewidth 3. In this paper we focus on the boundary case of treewidth 2. It was recently shown that the dimension is bounded if the cover graph is outerplanar (Felsner, Trotter, and Wiechert) or if it has pathwidth 2 (Biró, Keller, and Young). This can be interpreted as evidence that the dimension should be bounded more generally when the cover graph has treewidth 2. We show that it is indeed the case: Every such poset has dimension at most 1276.
cris.lastimport.wos | 2024-04-09T19:47:11Z | |
dc.abstract.en | In 1977, Trotter and Moore proved that a poset has dimension at most 3 whenever its cover graph is a forest, or equivalently, has treewidth at most 1. On the other hand, a well-known construction of Kelly shows that there are posets of arbitrarily large dimension whose cover graphs have treewidth 3. In this paper we focus on the boundary case of treewidth 2. It was recently shown that the dimension is bounded if the cover graph is outerplanar (Felsner, Trotter, and Wiechert) or if it has pathwidth 2 (Biró, Keller, and Young). This can be interpreted as evidence that the dimension should be bounded more generally when the cover graph has treewidth 2. We show that it is indeed the case: Every such poset has dimension at most 1276. | pl |
dc.affiliation | Wydział Matematyki i Informatyki : Zespół Katedr i Zakładów Informatyki Matematycznej | pl |
dc.contributor.author | Joret, Gwenaël | pl |
dc.contributor.author | Micek, Piotr - 142050 | pl |
dc.contributor.author | Trotter, William T. | pl |
dc.contributor.author | Wang, Ruidong | pl |
dc.contributor.author | Wiechert, Veit | pl |
dc.date.accessioned | 2018-04-10T13:59:10Z | |
dc.date.available | 2018-04-10T13:59:10Z | |
dc.date.issued | 2017 | pl |
dc.date.openaccess | 0 | |
dc.description.accesstime | w momencie opublikowania | |
dc.description.number | 2 | pl |
dc.description.physical | 185-234 | pl |
dc.description.version | ostateczna wersja wydawcy | |
dc.description.volume | 34 | pl |
dc.identifier.doi | 10.1007/s11083-016-9395-y | pl |
dc.identifier.eissn | 1572-9273 | pl |
dc.identifier.issn | 0167-8094 | pl |
dc.identifier.uri | https://ruj.uj.edu.pl/xmlui/handle/item/53128 | |
dc.language | eng | pl |
dc.language.container | eng | pl |
dc.rights | Udzielam licencji. Uznanie autorstwa 3.0 Polska | * |
dc.rights.licence | CC-BY | |
dc.rights.uri | http://creativecommons.org/licenses/by/3.0/pl/legalcode | * |
dc.share.type | inne | |
dc.subject.en | poset | pl |
dc.subject.en | dimension | pl |
dc.subject.en | treewidth | pl |
dc.subtype | Article | pl |
dc.title | On the dimension of posets with cover graphs of treewidth 2 | pl |
dc.title.journal | Order | pl |
dc.type | JournalArticle | pl |
dspace.entity.type | Publication |