Joret, Gwenael ; Micek, Piotr ; Trotter, William T. ; Wang, Ruidong ; Wiechert, Veit (2016-06-01)
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 dimen...An On-line competitive algorithm for coloring bipartite graphs without long induced paths
Micek, Piotr ; Wiechert, Veit (2016)
The existence of an on-line competitive algorithm for coloring bipartite graphs is a tantalizing open problem. So far there are only partial positive results for bipartite graphs with certain small forbidden graphs as induced subgraphs. We propose an on-line competitive coloring algorithm for P9-free bipartite graphs.