Given a connected graph $G$ and its vertex $x$, let $U_x(G)$ denote the universal cover of $G$ obtained by unfolding $G$ into a tree starting from $x$. Let $T=T(n)$ be the minimum number such that, for graphs $G$ and $H$ with at most $n$ vertices eac
h, the isomorphism of $U_x(G)$ and $U_y(H)$ surely follows from the isomorphism of these rooted trees truncated at depth $T$. Motivated by applications in theory of distributed computing, Norris [Discrete Appl. Math. 1995] asks if $T(n)le n$. We answer this question in the negative by establishing that $T(n)=(2-o(1))n$. Our solution uses basic tools of finite model theory such as a bisimulation version of the Immerman-Lander 2-pebble counting game. The graphs $G_n$ and $H_n$ we construct to prove the lower bound for $T(n)$ also show some other tight lower bounds. Both having $n$ vertices, $G_n$ and $H_n$ can be distinguished in 2-variable counting logic only with quantifier depth $(1-o(1))n$. It follows that color refinement, the classical procedure used in isomorphism testing and other areas for computing the coarsest equitable partition of a graph, needs $(1-o(1))n$ rounds to achieve color stabilization on each of $G_n$ and $H_n$. Somewhat surprisingly, this number of rounds is not enough for color stabilization on the disjoint union of $G_n$ and $H_n$, where $(2-o(1))n$ rounds are needed.
The isomorphism problem is known to be efficiently solvable for interval graphs, while for the larger class of circular-arc graphs its complexity status stays open. We consider the intermediate class of intersection graphs for families of circular ar
cs that satisfy the Helly property. We solve the isomorphism problem for this class in logarithmic space. If an input graph has a Helly circular-arc model, our algorithm constructs it canonically, which means that the models constructed for isomorphic graphs are equal.
A graph $G$ is 3-colorable if and only if it maps homomorphically to the complete 3-vertex graph $K_3$. The last condition can be checked by a $k$-consistency algorithm where the parameter $k$ has to be chosen large enough, dependent on $G$. Let $W(G
)$ denote the minimum $k$ sufficient for this purpose. For a non-3-colorable graph $G$, $W(G)$ is equal to the minimum $k$ such that $G$ can be distinguished from $K_3$ in the $k$-variable existential-positive first-order logic. We define the dynamic width of the 3-colorability problem as the function $W(n)=max_G W(G)$, where the maximum is taken over all non-3-colorable $G$ with $n$ vertices. The assumption $mathrm{NP} emathrm{P}$ implies that $W(n)$ is unbounded. Indeed, a lower bound $W(n)=Omega(loglog n/logloglog n)$ follows unconditionally from the work of Nesetril and Zhu on bounded treewidth duality. The Exponential Time Hypothesis implies a much stronger bound $W(n)=Omega(n/log n)$ and indeed we unconditionally prove that $W(n)=Omega(n)$. In fact, an even stronger statement is true: A first-order sentence distinguishing any 3-colorable graph on $n$ vertices from any non-3-colorable graph on $n$ vertices must have $Omega(n)$ variables. On the other hand, we observe that $W(G)le 3,alpha(G)+1$ and $W(G)le n-alpha(G)+1$ for every non-3-colorable graph $G$ with $n$ vertices, where $alpha(G)$ denotes the independence number of $G$. This implies that $W(n)lefrac34,n+1$, improving on the trivial upper bound $W(n)le n$. We also show that $W(G)>frac1{16}, g(G)$ for every non-3-colorable graph $G$, where $g(G)$ denotes the girth of $G$. Finally, we consider the function $W(n)$ over planar graphs and prove that $W(n)=Theta(sqrt n)$ in the case.
Establishing arc consistency on two relational structures is one of the most popular heuristics for the constraint satisfaction problem. We aim at determining the time complexity of arc consistency testing. The input structures $G$ and $H$ can be sup
posed to be connected colored graphs, as the general problem reduces to this particular case. We first observe the upper bound $O(e(G)v(H)+v(G)e(H))$, which implies the bound $O(e(G)e(H))$ in terms of the number of edges and the bound $O((v(G)+v(H))^3)$ in terms of the number of vertices. We then show that both bounds are tight up to a constant factor as long as an arc consistency algorithm is based on constraint propagation (like any algorithm currently known). Our argument for the lower bounds is based on examples of slow constraint propagation. We measure the speed of constraint propagation observed on a pair $G,H$ by the size of a proof, in a natural combinatorial proof system, that Spoiler wins the existential 2-pebble game on $G,H$. The proof size is bounded from below by the game length $D(G,H)$, and a crucial ingredient of our analysis is the existence of $G,H$ with $D(G,H)=Omega(v(G)v(H))$. We find one such example among old benchmark instances for the arc consistency problem and also suggest a new, different construction.
Given two structures $G$ and $H$ distinguishable in $fo k$ (first-order logic with $k$ variables), let $A^k(G,H)$ denote the minimum alternation depth of a $fo k$ formula distinguishing $G$ from $H$. Let $A^k(n)$ be the maximum value of $A^k(G,H)$ ov
er $n$-element structures. We prove the strictness of the quantifier alternation hierarchy of $fo 2$ in a strong quantitative form, namely $A^2(n)ge n/8-2$, which is tight up to a constant factor. For each $kge2$, it holds that $A^k(n)>log_{k+1}n-2$ even over colored trees, which is also tight up to a constant factor if $kge3$. For $kge 3$ the last lower bound holds also over uncolored trees, while the alternation hierarchy of $fo 2$ collapses even over all uncolored graphs. We also show examples of colored graphs $G$ and $H$ on $n$ vertices that can be distinguished in $fo 2$ much more succinctly if the alternation number is increased just by one: while in $Sigma_{i}$ it is possible to distinguish $G$ from $H$ with bounded quantifier depth, in $Pi_{i}$ this requires quantifier depth $Omega(n^2)$. The quadratic lower bound is best possible here because, if $G$ and $H$ can be distinguished in $fo k$ with $i$ quantifier alternations, this can be done with quantifier depth $n^{2k-2}$.
We consider straight line drawings of a planar graph $G$ with possible edge crossings. The emph{untangling problem} is to eliminate all edge crossings by moving as few vertices as possible to new positions. Let $fix(G)$ denote the maximum number of v
ertices that can be left fixed in the worst case. In the emph{allocation problem}, we are given a planar graph $G$ on $n$ vertices together with an $n$-point set $X$ in the plane and have to draw $G$ without edge crossings so that as many vertices as possible are located in $X$. Let $fit(G)$ denote the maximum number of points fitting this purpose in the worst case. As $fix(G)le fit(G)$, we are interested in upper bounds for the latter and lower bounds for the former parameter. For each $epsilon>0$, we construct an infinite sequence of graphs with $fit(G)=O(n^{sigma+epsilon})$, where $sigma<0.99$ is a known graph-theoretic constant, namely the shortness exponent for the class of cubic polyhedral graphs. To the best of our knowledge, this is the first example of graphs with $fit(G)=o(n)$. On the other hand, we prove that $fix(G)gesqrt{n/30}$ for all $G$ with tree-width at most 2. This extends the lower bound obtained by Goaoc et al. [Discrete and Computational Geometry 42:542-569 (2009)] for outerplanar graphs. Our upper bound for $fit(G)$ is based on the fact that the constructed graphs can have only few collinear vertices in any crossing-free drawing. To prove the lower bound for $fix(G)$, we show that graphs of tree-width 2 admit drawings that have large sets of collinear vertices with some additional special properties.
Given a planar graph $G$, we consider drawings of $G$ in the plane where edges are represented by straight line segments (which possibly intersect). Such a drawing is specified by an injective embedding $pi$ of the vertex set of $G$ into the plane. W
e prove that a wheel graph $W_n$ admits a drawing $pi$ such that, if one wants to eliminate edge crossings by shifting vertices to new positions in the plane, then at most $(2+o(1))sqrt n$ of all $n$ vertices can stay fixed. Moreover, such a drawing $pi$ exists even if it is presupposed that the vertices occupy any prescribed set of points in the plane. Similar questions are discussed for other families of planar graphs.
