On the dimension of posets with cover graphs of treewidth 2

2017
journal article
article
cris.lastimport.wos2024-04-09T19:47:11Z
dc.abstract.enIn 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.affiliationWydział Matematyki i Informatyki : Zespół Katedr i Zakładów Informatyki Matematycznejpl
dc.contributor.authorJoret, Gwenaëlpl
dc.contributor.authorMicek, Piotr - 142050 pl
dc.contributor.authorTrotter, William T.pl
dc.contributor.authorWang, Ruidongpl
dc.contributor.authorWiechert, Veitpl
dc.date.accessioned2018-04-10T13:59:10Z
dc.date.available2018-04-10T13:59:10Z
dc.date.issued2017pl
dc.date.openaccess0
dc.description.accesstimew momencie opublikowania
dc.description.number2pl
dc.description.physical185-234pl
dc.description.versionostateczna wersja wydawcy
dc.description.volume34pl
dc.identifier.doi10.1007/s11083-016-9395-ypl
dc.identifier.eissn1572-9273pl
dc.identifier.issn0167-8094pl
dc.identifier.urihttps://ruj.uj.edu.pl/xmlui/handle/item/53128
dc.languageengpl
dc.language.containerengpl
dc.rightsUdzielam licencji. Uznanie autorstwa 3.0 Polska*
dc.rights.licenceCC-BY
dc.rights.urihttp://creativecommons.org/licenses/by/3.0/pl/legalcode*
dc.share.typeinne
dc.subject.enposetpl
dc.subject.endimensionpl
dc.subject.entreewidthpl
dc.subtypeArticlepl
dc.titleOn the dimension of posets with cover graphs of treewidth 2pl
dc.title.journalOrderpl
dc.typeJournalArticlepl
dspace.entity.typePublication
Affiliations

* The migration of download and view statistics prior to the date of April 8, 2024 is in progress.

Views
0
Views per month
Downloads
joret_micek_trotter_wang_wiechert_on_the_dimension_of_posets_with_cover_graphs_2017.pdf
1