Informacja

Drogi użytkowniku, aplikacja do prawidłowego działania wymaga obsługi JavaScript. Proszę włącz obsługę JavaScript w Twojej przeglądarce.

Tytuł pozycji:

On the dimension of posets with cover graphs of treewidth 2

Tytuł:
On the dimension of posets with cover graphs of treewidth 2
Autorzy:
Trotter, William T.
Wiechert, Veit
Micek, Piotr
Wang, Ruidong
Joret, Gwenaël
Data publikacji:
2017
Słowa kluczowe:
poset
treewidth
dimension
Język:
angielski
ISBN, ISSN:
01678094
Prawa:
http://creativecommons.org/licenses/by/3.0/pl/legalcode
Udzielam licencji. Uznanie autorstwa 3.0 Polska
Dostawca treści:
Repozytorium Uniwersytetu Jagiellońskiego
Artykuł
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.

Ta witryna wykorzystuje pliki cookies do przechowywania informacji na Twoim komputerze. Pliki cookies stosujemy w celu świadczenia usług na najwyższym poziomie, w tym w sposób dostosowany do indywidualnych potrzeb. Korzystanie z witryny bez zmiany ustawień dotyczących cookies oznacza, że będą one zamieszczane w Twoim komputerze. W każdym momencie możesz dokonać zmiany ustawień dotyczących cookies