Tree-width of graphs in which any two cycles touch

Question

Let $G$ be a graph s.t. any two cycles $C_1, C_2 \subseteq G$ either have a common vertex or $G$ has an edge joining a vertex in $C_1$ to a vertex of $C_2$. Equivalently: for every cycle $C$ the graph obtained from $G$ by deleting $C$ and all neighbors of $C$ is acyclic. Let's denote the class of all such graphs by $\mathcal{G}$.

The cycle $C_n$, the complete graph $K_n$ and the complete bipartite graph $K_{s,t}$ are rather trivial examples of such graphs.

Are there constants $g, t$ such that all $G \in \mathcal{G}$ of girth at least $g$ (that is, all cycles of $G$ have length $> g$) have tree-width at most $t$?

UPDATE: As pointed out in the comments, the desired conclusion that $G$ has tree-width at most $t$ may as well be replaced by "contains at most $t$ disjoint cycles".

Answer 1

Here is another way to think about your problem. For each $g \geq 3$ let $\mathcal G_g$ be the graphs in $\mathcal G$ with girth at least $g$. For a graph $G$, let $\nu(G)$ be the maximum number of vertex-disjoint cycles of $G$, and for a graph class $\mathcal C$, let $\nu(\mathcal C):=\sup \{\nu(G) \mid G \in \mathcal C\}$. Then your question is equivalent to the following question:

Does there exist $g \geq 3$ such that $\nu(\mathcal G_g)$ is finite?

To see this, if $\nu(\mathcal G_g)=k$ for some $g$, then every $G \in \mathcal{G}_g$ has a feedback vertex set of size $O(k \log k)$ by the Erdős–Pósa theorem, and hence has treewidth $O(k \log k)$. Conversely, if $\nu(\mathcal G_g)$ is infinite for every $g$, then for each $g$ there are graphs in $\mathcal G_g$ with arbitrarily many vertex-disjoint cycles. Since there is always an edge between two disjoint cycles, this implies that there are graphs in $\mathcal G_g$ with arbitrarily large clique minors. Hence, $\mathcal G_g$ has unbounded treewidth for every $g \geq 3$.

David Eppstein has shown (see here) that there are graphs $G \in \mathcal G$ with arbitrarily high girth and with $\nu(G)=4$. It is unclear that there are graphs $G \in \mathcal G$ with arbitrarily high girth and with $\nu(G)=5$

Here is a modification of his construction that shows that there is a graph $G \in \mathcal G_{10}$ with $\nu(G)=5$. Let $C_1, \dots, C_5$ be long cycles and choose a red vertex $r_i$ and a blue vertex $b_i$ on each $C_i$ such that $r_i$ and $b_i$ are far apart on $C_i$. Observe that the edges of $K_5$ can be decomposed into a red $5$-cycle and a blue $5$-cycle. Therefore, we can add a $10$-cycle $C$ on the vertices $\{r_1, \dots, r_5\} \cup \{b_1, \dots, b_5\}$ such that for all distinct $i,j \in [5]$ there is an edge of $C$ between $\{r_i,b_i\}$ and $\{r_j,b_j\}$. Let $G$ be the resulting graph. Note that $C$ is the only cycle of $G$ which does not use an edge of any $C_i$. Every other cycle uses an edge of some $C_i$ (and hence many edges of $C_i$). Therefore, $G$ has girth $10$. Observe that every cycle of $G$ must include both $r_i$ and $b_i$ for some $i \in [5]$. Since there is an edge between $\{r_i,b_i\}$ and $\{r_j,b_j\}$ for all distinct $i,j \in [5]$, every two cycles of $G$ intersect or have an edge between them. Finally, clearly $\nu(G)=5$. Note that this example almost has arbitrarily large girth ($C$ is the only short cycle).

Answer 2

This is not a complete answer but it suggests that you have not made your statement strong enough: Your condition that all cycles touch means that the set of all cycles forms a bramble. By the characterization of treewidth via brambles, if these graphs have tree-width at most t then the cycles have a hitting set (a feedback vertex set) of size at most t+1. So if your assumptions imply that the treewidth is bounded, they also imply that the feedback vertex number is bounded, a stronger condition in general than bounded treewidth.

Answer 3

I tried to prove the statement for a while and I think I managed to narrow it down to one particularly difficult case. In the end, it led me to a counter example, showing there are no such values $g$ and $t$. This came as a bit of a surprise for me. The construction goes as follows.

(1) For every $n \geq 1$ there is a cycle $C$ and a labeling $\varphi: V(C) \to [n+1]$ such that $|\varphi^{-1}(n+1)| = 1$ and for every non-trivial path $P = xPy \subseteq C$ and all $i < \min\{\varphi(x), \varphi(y)\}$, $P$ contains a vertex labeled $i$.

proof: By induction on $n$, the case $n =1$ being trivial. In the inductive step, start from $(C, \varphi)$ for $n$, and obtain $C'$ from $C$ by subdividing every edge. Let $\varphi'(x) = \varphi(x)+1$ for $x \in C$ and $\varphi'(x) = 1$ for $x \in C' \setminus C$.

(2) Let now $n$ be given. Start with the disjoin union of $n$ copies $C_1, \ldots, C_n$ of the labled cycle from (1). Subdivide every edge of each cycle $n$ times, leaving the new vertices unlabeled. For every $i$, let $x_i \in C_i$ be the unique vertex labeled $n+1$. Join $x_i$ to all vertices on $\bigcup_{i < j \leq n} C_j$ labeled $i$.

It's easy to see that every cycle $D$ must contain at least one of $x_1, \ldots, x_n$. Let the minimum $1 \leq i \leq n$ with $x_i \in D$ be the index $\mathcal{idx}(D)$ of $D$. Moreover, we can see that $D$ contains a neighbor of $x_i$ for all $i < \mathcal{idx}(D)$.

Let $D_1, D_2$ be two cycles of $G$, wlog $\mathcal{idx}(D_1) \leq \mathcal{idx}(D_2)$. If equality holds, then $D_1 \cap D_2$ is non-empty. If $\mathcal{idx}(D_1) <\mathcal{idx}(D_2)$, then there is an edge from $D_1$ to $D_2$. Either way, any two cycles touch.

Moreover, since $G$ has disjoint pairwise touching cycles $C_1, \ldots , C_n$, the tree-width of $G$ is at least $n-1$. Since every cycle must contain an edge of at least one cycle $C_i$, the girth of $G$ is at least $n$.