# Tree-width of graphs in which any two cycles touch

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

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

• So far the maximum number of vertex disjoint cycles I can find (with all cycles touching and arbitrarily large girth) is four; see 11011110.github.io/blog/2020/10/26/graphs-whose-cycles.html for details. The same graphs also have feedback vertex number four. Oct 26, 2020 at 23:27
• @DavidEppstein Thanks for this! I have been thinking a bit about the problem as well. The complete bipartite graphs work for girth 4, and I was trying some algebraic constructions with high girth, but they all seem to not have the property, Oct 26, 2020 at 23:59
• @DavidEppstein I modified your construction to (almost) get a graph with high girth, all cycles touching, and cycle packing number 5. See above. Oct 27, 2020 at 10:25
• This is great! I haven't done much maths since I finished my PhD two years ago, it's fantastic to have such esteemed colleagues join me on this seemingly innocent problem! For the context I had in mind, pushing $\nu(G)$ is more essential than the girth. Oct 27, 2020 at 10:59

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

• Very nice! I think you should accept your own answer. Also, you should probably let David Eppstein know; I am not sure how often he checks MO. Nov 3, 2020 at 2:40

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.

• Yes, David, this is an equivalent condition. Perhaps it is better to phrase the problem in this equivalent form, since it does not require recourse to the "external" concept of tree-width. Thank you! Oct 26, 2020 at 18:41