<p>If I understood your statement correctly, then it is false:</p>
<p>In a graph of maximum degree <span class="math-container">$3$</span> the <span class="math-container">$4$</span>-connected components are all single vertices (and therefore planar AND of treewidth <span class="math-container">$\leq 1$</span>). However we can make graphs of maximum degree 3 that contain arbitrarily large cliques as minors.</p>

CC BY-SA 4.0
2020-10-16T06:52:12.123Z
the 3-clique sum decomposition is perhaps what the OP is referring to. Wouldn’t we get a decomposition into a $K_4$ and a graph with minimum degree at $4$ the first time we try the decomposition. Further would this be a strong $3$ cut in the sense of Demaine et al?
SamiD
CC BY-SA 4.0
2020-10-01T03:30:53.833Z
2020-10-01T03:30:53.833Z
daniello
<p>We know that for a single-crossing graph <em>H</em> of size <em>h</em>, there exists a constant <em>c<sub>h</sub></em> whose value depends only on <em>h</em>, such that every four-connected component of an <em>H</em>-minor-free graph is either a planar graph or of treewidth at most <em>c<sub>h</sub></em>.</p>
<p>I would like to know if some sort of the reverse of this also holds. That is, can we say for every such graph <em>G</em> whose four-connected components are of treewidth is at most <em>w</em> or a planar graph, there exists a constant <em>c<sub>w</sub></em> whose value depends only on <em>w</em> and single-crossing graphs <em>H<sub>1</sub>, H<sub>2</sub>, ..., H<sub>l</sub></em> each of size at most <em>c<sub>w</sub></em>, such that <em>G</em> belongs to the union of <em>H_i</em>-minor free-graphs for each <em>i</em> in <em>1, 2, ..., l</em>?</p>

CC BY-SA 4.0
2020-10-01T03:07:28.277Z
When you say 4-connected do you mean wrt edge cuts or vertex cuts?
daniello
CC BY-SA 4.0
2020-10-03T21:57:36.270Z
I mean vertex connectivity.
Rahul Jain
<graph-theory>
Decomposing Single Crossing Minor Free graphs
Rahul Jain
# Decomposing Single Crossing Minor Free graphs

(Asked by: username_0 on 2020-09-27)

We know that for a single-crossing graph *H* of size *h*, there exists a constant *ch* whose value depends only on *h*, such that every four-connected component of an *H*-minor-free graph is either a planar graph or of treewidth at most *ch*.

I would like to know if some sort of the reverse of this also holds. That is, can we say for every such graph *G* whose four-connected components are of treewidth is at most *w* or a planar graph, there exists a constant *cw* whose value depends only on *w* and single-crossing graphs *H1, H2, ..., Hl* each of size at most *cw*, such that *G* belongs to the union of *H\_i*-minor free-graphs for each *i* in *1, 2, ..., l*?

**Tags:** graph-theory
> **Comments:**
> **username_1**: When you say 4-connected do you mean wrt edge cuts or vertex cuts?  
> **username_0**: I mean vertex connectivity.  

---

## 1 answers

### Answer by username_1 on 2020-10-01. Score: 3

If I understood your statement correctly, then it is false:

In a graph of maximum degree $3$ the $4$-connected components are all single vertices (and therefore planar AND of treewidth $\leq 1$). However we can make graphs of maximum degree 3 that contain arbitrarily large cliques as minors.

> **Comments:**
> **username_2**: the 3-clique sum decomposition is perhaps what the OP is referring to. Wouldn’t we get a decomposition into a $K_4$ and a graph with minimum degree at $4$ the first time we try the decomposition. Further would this be a strong $3$ cut in the sense of Demaine et al?  

---

