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?

$\endgroup$
2
  • $\begingroup$ When you say 4-connected do you mean wrt edge cuts or vertex cuts? $\endgroup$ – daniello Oct 1 '20 at 3:07
  • $\begingroup$ I mean vertex connectivity. $\endgroup$ – Rahul Jain Oct 3 '20 at 21:57
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.

$\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 '20 at 6:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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