vol. 22 no. 4


1. (Open) packing number of some graph products

Doost Ali Mojdeh ; Iztok Peterin ; Babak Samadi ; Ismael G. Yero.
The packing number of a graph $G$ is the maximum number of closedneighborhoods of vertices in $G$ with pairwise empty intersections. Similarly,the open packing number of $G$ is the maximum number of open neighborhoods in$G$ with pairwise empty intersections. We consider the packing and open packingnumbers on graph products. In particular we give a complete solution withrespect to some properties of factors in the case of lexicographic and rootedproducts. For Cartesian, strong and direct products, we present several lowerand upper bounds on these parameters.

2. A Type System Describing Unboundedness

Paweł Parys.
We consider nondeterministic higher-order recursion schemes as recognizers of languages of finite words or finite trees. We propose a type system that allows to solve the simultaneous-unboundedness problem (SUP) for schemes, which asks, given a set of letters A and a scheme G, whether it is the case that for every number n the scheme accepts a word (a tree) in which every letter from A appears at least n times. Using this type system we prove that SUP is (m-1)-EXPTIME-complete for word-recognizing schemes of order m, and m-EXPTIME-complete for tree-recognizing schemes of order m. Moreover, we establish the reflection property for SUP: out of an input scheme G one can create its enhanced version that recognizes the same language but is aware of the answer to SUP.

3. A Büchi-Elgot-Trakhtenbrot theorem for automata with MSO graph storage

Joost Engelfriet ; Heiko Vogler.
We introduce MSO graph storage types, and call a storage type MSO-expressibleif it is isomorphic to some MSO graph storage type. An MSO graph storage typehas MSO-definable sets of graphs as storage configurations and as storagetransformations. We consider sequential automata with MSO graph storage andassociate with each such automaton a string language (in the usual way) and agraph language; a graph is accepted by the automaton if it represents a correctsequence of storage configurations for a given input string. For each MSO graphstorage type, we define an MSO logic which is a subset of the usual MSO logicon graphs. We prove a Büchi-Elgot-Trakhtenbrot theorem, both for the stringcase and the graph case. Moreover, we prove that (i) each MSO graphtransduction can be used as storage transformation in an MSO graph storagetype, (ii) every automatic storage type is MSO-expressible, and (iii) thepushdown operator on storage types preserves the property ofMSO-expressibility. Thus, the iterated pushdown storage types areMSO-expressible.

4. Evacuating Robots from a Disk Using Face-to-Face Communication

Jurek Czyzowicz ; Konstantinos Georgiou ; Evangelos Kranakis ; Lata Narayanan ; Jarda Opatrny ; Birgit Vogtenhuber.
Assume that two robots are located at the centre of a unit disk. Their goalis to evacuate from the disk through an exit at an unknown location on theboundary of the disk. At any time the robots can move anywhere they choose onthe disk, independently of each other, with maximum speed $1$. The robots cancooperate by exchanging information whenever they meet. We study algorithms forthe two robots to minimize the evacuation time: the time when both robots reachthe exit. In [CGGKMP14] the authors gave an algorithm defining trajectories for the tworobots yielding evacuation time at most $5.740$ and also proved that anyalgorithm has evacuation time at least $3+ \frac{\pi}{4} + \sqrt{2} \approx5.199$. We improve both the upper and lower bound on the evacuation time of aunit disk. Namely, we present a new non-trivial algorithm whose evacuation timeis at most $5.628$ and show that any algorithm has evacuation time at least $3+\frac{\pi}{6} + \sqrt{3} \approx 5.255$. To achieve the upper bound, wedesigned an algorithm which proposes a forced meeting between the two robots,even if the exit has not been found by either of them. We also show that such astrategy is provably optimal for a related problem of searching for an exitplaced at the vertices of a regular hexagon.

5. Taking-and-merging games as rewrite games

Eric Duchêne ; Victor Marsault ; Aline Parreau ; Michel Rigo.
This work is a contribution to the study of rewrite games. Positions arefinite words, and the possible moves are defined by a finite number of localrewriting rules. We introduce and investigate taking-and-merging games, thatis, where each rule is of the form a^k->epsilon. We give sufficient conditions for a game to be such that the losing positions(resp. the positions with a given Grundy value) form a regular language or acontext-free language. We formulate several related open questions in parallelwith the famous conjecture of Guy about the periodicity of the Grundy functionof octal games. Finally we show that more general rewrite games quickly lead to undecidableproblems. Namely, it is undecidable whether there exists a winning position ina given regular language, even if we restrict to games where each move strictlyreduces the length of the current position. We formulate several related openquestions in parallel with the famous conjecture of Guy about the periodicityof the Grundy function of octal games.

6. Even cycles and perfect matchings in claw-free plane graphs

Shanshan Zhang ; Xiumei Wang ; Jinjiang Yuan.
Lov{á}sz showed that a matching covered graph $G$ has an ear decompositionstarting with an arbitrary edge of $G$. Let $G$ be a graph which has a perfectmatching. We call $G$ cycle-nice if for each even cycle $C$ of $G$, $G-V(C)$has a perfect matching. If $G$ is a cycle-nice matching covered graph, then $G$has ear decompositions starting with an arbitrary even cycle of $G$. In thispaper, we characterize cycle-nice claw-free plane graphs. We show that the onlycycle-nice simple 3-connected claw-free plane graphs are $K_4$, $W_5$ and$\overline C_6$. Furthermore, every cycle-nice 2-connected claw-free planegraph can be obtained from a graph in the family ${\cal F}$ by a sequence ofthree types of operations, where ${\cal F}$ consists of even cycles, a diamond,$K_4$, and $\overline C_6$.

7. A Double Exponential Lower Bound for the Distinct Vectors Problem

Marcin Pilipczuk ; Manuel Sorge.
In the (binary) Distinct Vectors problem we are given a binary matrix A withpairwise different rows and want to select at most k columns such that,restricting the matrix to these columns, all rows are still pairwise different.A result by Froese et al. [JCSS] implies a 2^2^(O(k)) * poly(|A|)-timebrute-force algorithm for Distinct Vectors. We show that this running timebound is essentially optimal by showing that there is a constant c such thatthe existence of an algorithm solving Distinct Vectors with running time2^(O(2^(ck))) * poly(|A|) would contradict the Exponential Time Hypothesis.

8. Extension Complexity, MSO Logic, and Treewidth

Petr Kolman ; Martin Koutecký ; Hans Raj Tiwary.
We consider the convex hull $P_{\varphi}(G)$ of all satisfying assignments ofa given MSO formula $\varphi$ on a given graph $G$. We show that there existsan extended formulation of the polytope $P_{\varphi}(G)$ that can be describedby $f(|\varphi|,\tau)\cdot n$ inequalities, where $n$ is the number of verticesin $G$, $\tau$ is the treewidth of $G$ and $f$ is a computable functiondepending only on $\varphi$ and $\tau.$ In other words, we prove that the extension complexity of $P_{\varphi}(G)$ islinear in the size of the graph $G$, with a constant depending on the treewidthof $G$ and the formula $\varphi$. This provides a very general yet very simplemeta-theorem about the extension complexity of polytopes related to a wideclass of problems and graphs. As a corollary of our main result, we obtain ananalogous result % for the weaker MSO$_1$ logic on the wider class of graphs ofbounded cliquewidth. Furthermore, we study our main geometric tool which we term the glued productof polytopes. While the glued product of polytopes has been known since the'90s, we are the first to show that it preserves decomposability andboundedness of treewidth of the constraint matrix. This implies that ourextension of $P_\varphi(G)$ is decomposable and has a constraint matrix ofbounded treewidth; so far only few classes of polytopes are known to bedecomposable. These properties make our extension useful in the construction ofalgorithms.

9. Two lower bounds for $p$-centered colorings

Loïc Dubois ; Gwenaël Joret ; Guillem Perarnau ; Marcin Pilipczuk ; François Pitois.
Given a graph $G$ and an integer $p$, a coloring $f : V(G) \to \mathbb{N}$ is\emph{$p$-centered} if for every connected subgraph $H$ of $G$, either $f$ usesmore than $p$ colors on $H$ or there is a color that appears exactly once in$H$. The notion of $p$-centered colorings plays a central role in the theory ofsparse graphs. In this note we show two lower bounds on the number of colorsrequired in a $p$-centered coloring. First, we consider monotone classes of graphs whose shallow minors haveaverage degree bounded polynomially in the radius, or equivalently (by a resultof Dvo\v{r}ák and Norin), admitting strongly sublinear separators. Weconstruct such a class such that $p$-centered colorings require a number ofcolors super-polynomial in $p$. This is in contrast with a recent result ofPilipczuk and Siebertz, who established a polynomial upper bound in the specialcase of graphs excluding a fixed minor. Second, we consider graphs of maximum degree $\Delta$. D\k{e}bski, Felsner,Micek, and Schröder recently proved that these graphs have $p$-centeredcolorings with $O(\Delta^{2-1/p} p)$ colors. We show that there are graphs ofmaximum degree $\Delta$ that require $\Omega(\Delta^{2-1/p} p\ln^{-1/p}\Delta)$ colors in any $p$-centered coloring, thus matching theirupper bound up to a logarithmic factor.

10. The number of distinct adjacent pairs in geometrically distributed words

Margaret Archibald ; Aubrey Blecher ; Charlotte Brennan ; Arnold Knopfmacher ; Stephan Wagner ; Mark Ward.
A sequence of geometric random variables of length $n$ is a sequence of $n$independent and identically distributed geometric random variables ($\Gamma_1,\Gamma_2, \dots, \Gamma_n$) where $\mathbb{P}(\Gamma_j=i)=pq^{i-1}$ for$1~\leq~j~\leq~n$ with $p+q=1.$ We study the number of distinct adjacent twoletter patterns in such sequences. Initially we directly count the number ofdistinct pairs in words of short length. Because of the rapid growth of thenumber of word patterns we change our approach to this problem by obtaining anexpression for the expected number of distinct pairs in words of length $n$. Wealso obtain the asymptotics for the expected number as $n \to \infty$.

11. A Note on Graphs of Dichromatic Number 2

Raphael Steiner.
Neumann-Lara and Škrekovski conjectured that every planar digraph is 2-colourable. We show that this conjecture is equivalent to the more general statement that all oriented K_5-minor-free graphs are 2-colourable.

12. A new sufficient condition for a Digraph to be Hamiltonian-A proof of Manoussakis Conjecture

Samvel Kh. Darbinyan.
Y. Manoussakis (J. Graph Theory 16, 1992, 51-59) proposed the followingconjecture. \noindent\textbf{Conjecture}. {\it Let $D$ be a 2-strongly connected digraphof order $n$ such that for all distinct pairs of non-adjacent vertices $x$, $y$and $w$, $z$, we have $d(x)+d(y)+d(w)+d(z)\geq 4n-3$. Then $D$ is Hamiltonian.} In this paper, we confirm this conjecture. Moreover, we prove that if adigraph $D$ satisfies the conditions of this conjecture and has a pair ofnon-adjacent vertices $\{x,y\}$ such that $d(x)+d(y)\leq 2n-4$, then $D$contains cycles of all lengths $3, 4, \ldots , n$.

13. The LexCycle on $\overline{P_{2}\cup P_{3}}$-free Cocomparability Graphs

Xiao-Lu Gao ; Shou-Jun Xu.
A graph $G$ is a cocomparability graph if there exists an acyclic transitiveorientation of the edges of its complement graph $\overline{G}$. LBFS$^{+}$ isa variant of the generic Lexicographic Breadth First Search (LBFS), which usesa specific tie-breaking mechanism. Starting with some ordering $\sigma_{0}$ of$G$, let $\{\sigma_{i}\}_{i\geq 1}$ be the sequence of orderings such that$\sigma_{i}=$LBFS$^{+}(G, \sigma_{i-1})$. The LexCycle($G$) is defined as themaximum length of a cycle of vertex orderings of $G$ obtained via such asequence of LBFS$^{+}$ sweeps. Dusart and Habib conjectured in 2017 thatLexCycle($G$)=2 if $G$ is a cocomparability graph and proved it holds forinterval graphs. In this paper, we show that LexCycle($G$)=2 if $G$ is a$\overline{P_{2}\cup P_{3}}$-free cocomparability graph, where a$\overline{P_{2}\cup P_{3}}$ is the graph whose complement is the disjointunion of $P_{2}$ and $P_{3}$. As corollaries, it's applicable for diamond-freecocomparability graphs, cocomparability graphs with girth at least 4, as wellas interval graphs.