On the Dimension of Posets with Cover Graphs of Treewidth 2

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.     

A Note on the Cops and Robber Game on Graphs Embedded in Non-Orientable Surfaces

We consider the two-player, complete information game of Cops and Robber played on undirected, finite, reflexive graphs. A number of cops and one robber are positioned on vertices and take turns in sliding along edges. The cops win if, after a move, a cop and the robber are on the same vertex. The minimum number of cops needed to catch the robber on a graph is called the cop number of that graph. Let c(g) be the supremum over all cop numbers of graphs embeddable in a closed orientable surface of genus g, and likewise ${\tilde c(g)}$ for non-orientable surfaces. It is known (Andreae, 1986) that, for a fixed surface, the maximum over all cop numbers of graphs embeddable in this surface is finite. More precisely, Quilliot (1985) showed that c(g) ≤ 2g + 3, and Schröder (2001) sharpened this to ${c(g)\le \frac32g + 3}$ . In his paper, Andreae gave the bound ${\tilde c(g) \in O(g)}$ with a weak constant, and posed the question whether a stronger bound can be obtained. Nowakowski & Schröder (1997) obtained ${\tilde c(g) \le 2g+1}$ . In this short note, we show ${\tilde c(g) \leq c(g-1)}$ , for any g ≥ 1. As a corollary, using Schröder’s results, we obtain the following: the maximum cop number of graphs embeddable in the projective plane is 3, the maximum cop number of graphs embeddable in the Klein Bottle is at most 4, ${\tilde c(3) \le 5}$ , and ${\tilde c(g) \le \frac32g + 3/2}$ for all other g.     

Boxicity of Graphs on Surfaces

The boxicity of a graph G = (V, E) is the least integer k for which there exist k interval graphs G _i  = (V, E _i ), 1 ≤ i ≤ k, such that ${E = E_1 \cap \cdots \cap E_k}$ . Scheinerman proved in 1984 that outerplanar graphs have boxicity at most two and Thomassen proved in 1986 that planar graphs have boxicity at most three. In this note we prove that the boxicity of toroidal graphs is at most 7, and that the boxicity of graphs embeddable in a surface Σ of genus g is at most 5g + 3. This result yields improved bounds on the dimension of the adjacency poset of graphs on surfaces.     

Trees with Given Stability Number and Minimum Number of Stable Sets

We study the structure of trees minimizing their number of stable sets for given order n and stability number α. Our main result is that the edges of a non-trivial extremal tree can be partitioned into n ? α stars, each of size \({\lceil\frac{n-1}{n-\alpha}\rceil}\) or \({\lfloor\frac{n-1}{n-\alpha}\rfloor}\) , so that every vertex is included in at most two distinct stars, and the centers of these stars form a stable set of the tree.     

Kupfer

Ohne Zusammenfassung     

Tree-width and dimension

Over the last 30 years, researchers have investigated connections between dimension for posets and planarity for graphs. Here we extend this line of research to the structural graph theory parameter tree-width by proving that the dimension of a finite poset is bounded in terms of its height and the tree-width of its cover graph.     

First-Fit is Linear on Posets Excluding Two Long Incomparable Chains

A poset is (r+s)(\underline{r}+\underline{s})-free if it does not contain two incomparable chains of size r and s, respectively. We prove that when r and s are at least 2, the First-Fit algorithm partitions every (r+s)(\underline{r}+\underline{s})-free poset P into at most 8(r − 1)(s − 1)w chains, where w is the width of P. This solves an open problem of Bosek et al. (SIAM J Discrete Math 23(4):1992–1999, 2010).