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".



Tree-width of graphs in which any two cycles touch
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$.


