3
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • $\begingroup$ When you say 4-connected do you mean wrt edge cuts or vertex cuts? $\endgroup$
    – daniello
    Oct 1, 2020 at 3:07
  • $\begingroup$ I mean vertex connectivity. $\endgroup$
    – Rahul Jain
    Oct 3, 2020 at 21:57

1 Answer 1

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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? $\endgroup$
    – SamiD
    Oct 16, 2020 at 6:52

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.