vol. 27:2

---

1. Eulerian $k$-dominating reconfiguration graphs

M. E. Messinger ; A. Porter.

For a graph $G$, the vertices of the $k$-dominating graph, denoted $\mathcal{D}_k(G)$, correspond to the dominating sets of $G$ with cardinality at most $k$. Two vertices of $\mathcal{D}_k(G)$ are adjacent if and only if the corresponding dominating sets in $G$ can be obtained from one other by adding or removing a single vertex of $G$. Since $\mathcal{D}_k(G)$ is not necessarily connected when $k < |V(G)|$, much research has focused on conditions under which $\mathcal{D}_k(G)$ is connected and recent work has explored the existence of Hamilton paths in the $k$-dominating graph. We consider the complementary problem of determining the conditions under which the $k$-dominating graph is Eulerian. In the case where $k = |V(G)|$, we characterize those graphs $G$ for which $\mathcal{D}_k(G)$ is Eulerian. In the case where $k$ is restricted, we determine for a number of graph classes, the conditions under which the $k$-dominating graph is Eulerian.

---

2. $\mathcal{S}$-adic characterization of minimal dendric shifts

France Gheeraert ; Julien Leroy.

Dendric shifts are defined by combinatorial restrictions of the extensions of the words in their languages. This family generalizes well-known families of shifts such as Sturmian shifts, Arnoux-Rauzy shifts and codings of interval exchange transformations. It is known that any minimal dendric shift has a primitive $\mathcal{S}$-adic representation where the morphisms in $\mathcal{S}$ are positive tame automorphisms of the free group generated by the alphabet. In this paper we give an $\mathcal{S}$-adic characterization of this family by means of two finite graphs. As an application, we are able to decide whether a shift space generated by a uniformly recurrent morphic word is (eventually) dendric.

---

3. Hypergraph Representation via Axis-Aligned Point-Subspace Cover

Oksana Firman ; Joachim Spoerhase.

We propose a new representation of $k$-partite, $k$-uniform hypergraphs, that is, a hypergraph with a partition of vertices into $k$ parts such that each hyperedge contains exactly one vertex of each type; we call them $k$-hypergraphs for short. Given positive integers $\ell, d$, and $k$ with $\ell\leq d-1$ and $k={d\choose\ell}$, any finite set $P$ of points in $\mathbb{R}^d$ represents a $k$-hypergraph $G_P$ as follows. Each point in $P$ is covered by $k$ many axis-aligned affine $\ell$-dimensional subspaces of $\mathbb{R}^d$, which we call $\ell$-subspaces for brevity and which form the vertex set of $G_P$. We interpret each point in $P$ as a hyperedge of $G_P$ that contains each of the covering $\ell$-subspaces as a vertex. The class of \emph{$(d,\ell)$-hypergraphs} is the class of $k$-hypergraphs that can be represented in this way. The resulting classes of hypergraphs are fairly rich: Every $k$-hypergraph is a $(k,k-1)$-hypergraph. On the other hand, $(d,\ell)$-hypergraphs form a proper subclass of the class of all $k$-hypergraphs for $\ell<d-1$. In this paper we give a natural structural characterization of $(d,\ell)$-hypergraphs based on vertex cuts. This characterization leads to a poly\-nomial-time recognition algorithm that decides for a given $k$-hypergraph whether or not it is a $(d,\ell)$-hypergraph and that computes a representation if existing. We assume that the dimension $d$ is constant and that the partitioning of the vertex set is prescribed.

---

4. On the on-line coloring of unit interval graphs with proper interval representation

Israel R. Curbelo ; Hannah R. Malko.

We define the problem as a two-player game between Algorithm and Builder. The game is played in rounds. Each round, Builder presents an interval that is neither contained in nor contains any previously presented interval. Algorithm immediately and irrevocably assigns the interval a color that has not been assigned to any interval intersecting it. The set of intervals form an interval representation for a unit interval graph and the colors form a proper coloring of that graph. For every positive integer $\omega$, we define the value $R(\omega)$ as the maximum number of colors for which Builder has a strategy that forces Algorithm to use $R(\omega)$ colors with the restriction that the unit interval graph constructed cannot contain a clique of size $\omega+1$. In 1981, Chrobak and \'{S}lusarek showed that $R(\omega)\leq2\omega -1$. In 2005, Epstein and Levy showed that $R(\omega)\geq\lfloor{3\omega/2\rfloor}$. This problem remained unsolved for $\omega\geq 3$. In 2023, Biró and Curbelo showed that $R(3)=5$. In this paper, we show that $R(4)=7$

---

5. From Tutte to Floater and Gotsman: On the Resolution of Planar Straight-line Drawings and Morphs

Giuseppe Di Battista ; Fabrizio Frati.

The algorithm of Tutte for constructing convex planar straight-line drawings and the algorithm of Floater and Gotsman for constructing planar straight-line morphs are among the most popular graph drawing algorithms. In this paper, focusing on maximal plane graphs, we prove upper and lower bounds on the resolution of the planar straight-line drawings produced by Floater's algorithm, which is a broad generalization of Tutte's algorithm. Further, we use such results in order to prove a lower bound on the resolution of the drawings of maximal plane graphs produced by Floater and Gotsman's morphing algorithm. Finally, we show that such a morphing algorithm might produce drawings with exponentially-small resolution, even when transforming drawings with polynomial resolution.

---

6. Treewidth 2 in the Planar Graph Product Structure Theorem

Marc Distel ; Kevin Hendrey ; Nikolai Karol ; David R. Wood ; Jung Hon Yip.

We prove that every planar graph is contained in $H_1\boxtimes H_2\boxtimes K_2$ for some graphs $H_1$ and $H_2$ both with treewidth 2. This resolves a question of Liu, Norin and Wood [arXiv:2410.20333]. We also show this result is best possible: for any $c \in \mathbb{N}$, there is a planar graph $G$ such that for any tree $T$ and graph $H$ with $\text{tw}(H) \leqslant 2$, $G$ is not contained in $H \boxtimes T \boxtimes K_c$.

---

7. A polynomial bound on the number of minimal separators and potential maximal cliques in $P_6$-free graphs of bounded clique number

Marcin Pilipczuk ; Paweł Rzążewski.

In this note we show a polynomial bound on the number of minimal separators and potential maximal cliques in $P_6$-free graphs of bounded clique number.

---