3
$\begingroup$

Let $G$ and $H$ be graphs with the following relationship: for some $k$, after you perform at least $k$ arbitrary subdivisions of the edges of $G$ (or the edges produced through subdivision), $H$ must be a minor. What do you call the relationship between $G$ and $H$?

For example, consider a claw with each edge subdivided once and a claw with one edge subdivided twice. You can subdivide any edge of the former to produce a graph for which the latter is a minor $(k = 1)$. Is anyone writing about this or has it been given a name?

| cite | improve this question | |
$\endgroup$
  • $\begingroup$ Are you sure you are stating this correctly? Isn't the first paragraph simply "$H$ is a minor of $G$"? Why not add a bunch of isolated vertices, making $k$ irrelevant? $\endgroup$ – Andrew D. King Jun 13 '11 at 16:51
  • $\begingroup$ Are you looking for topological minor? $\endgroup$ – Aaron Sterling Jun 13 '11 at 19:27
  • $\begingroup$ @Andrew: you're right, the first paragraph does have a misstatement. I'll edit. $\endgroup$ – Eli Jun 13 '11 at 19:50
  • 2
    $\begingroup$ Is this a correct way to rephrase the relationship you want to describe: "H is a minor of almost all subdivisions of G," where "almost all" means "all but finitely many." $\endgroup$ – Robin Kothari Jun 13 '11 at 23:08
  • $\begingroup$ @Robin, I think the condition is weaker: after fixing some $k$, after he construct the upward set, he's requiring that $H$ be a minor, for all such sets. $\endgroup$ – Suresh Venkat Jun 14 '11 at 11:26

Your Answer

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

Browse other questions tagged or ask your own question.