7
$\begingroup$

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

$\endgroup$

3 Answers 3

5
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$ Oct 26, 2020 at 23:27
  • $\begingroup$ @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, $\endgroup$
    – Tony Huynh
    Oct 26, 2020 at 23:59
  • $\begingroup$ @DavidEppstein I modified your construction to (almost) get a graph with high girth, all cycles touching, and cycle packing number 5. See above. $\endgroup$
    – Tony Huynh
    Oct 27, 2020 at 10:25
  • $\begingroup$ 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. $\endgroup$ Oct 27, 2020 at 10:59
3
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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! $\endgroup$ Oct 26, 2020 at 18:41
3
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Tony Huynh
    Nov 3, 2020 at 2:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.