3
$\begingroup$

I believe this is true:

Suppose $G$ is a graph. If $G$ has a subdivision of a large binary tree, prove that $G$ has an induced subgraph which is a subdivision of a large binary tree or the line graph of a subdivision of a large binary tree.

However, I think it is very difficult to prove in general, so I was hoping to do it for the case when $G$ has bounded treewidth (or say really small treewidth). Any ideas for those cases? Thank you!

[EDIT: I initially forgot the word subdvision in the question]

[EDIT2: PROVED, someone can delete]

$\endgroup$
2
  • $\begingroup$ Why don't you just post a brief description of your answer, instead of requesting deletion? $\endgroup$
    – S. Carnahan
    Apr 13, 2014 at 6:13
  • $\begingroup$ Sure, i'll do that in a bit $\endgroup$ Apr 13, 2014 at 17:16

1 Answer 1

1
$\begingroup$

I'll just give a very brief sketch.

Find a large subdivided binary tree $T$ with branch vertices far apart and minimize its number of edges. This should be possible by tweaking 'far apart' and 'large' in accordance with the tree width.

Every edge spanned by $T$ but not in $T$ lies in the neighbourhood of a branch vertex $v$ of $T$. Case analysis gives desired structures locally:

  • one edge in $N(v)$: it's the linegraph of a subdivided claw
  • two edges in $N(v)$: remove $v$ it's a subdivided claw
  • three edges in $N(v)$: remove $v$ it's the linegraph of a subdivided claw

Now you have large graph $T$ that is a mixture of a subdivided binary tree and a linegraph of a subdivided binary tree. Since it is large enough you find branch vertices of the same type often enough.

Sorry, I had a longer answer that my pc forgot about. I'll elaborate if you have further question.

$\endgroup$
10
  • $\begingroup$ Sorry, I edited the question - I meant something else. You are of course right for what I initially wrote. $\endgroup$ Feb 17, 2014 at 18:24
  • $\begingroup$ I think there is another counterexample for this version too: Start with a triangle. i) add an edge to every vertex of degree one. ii) add a triangle to every vertex of degree 2. repeat i) and ii) until your graph is large enough. Basically, the graph looks like a binary tree, but every vertex is blown up to be a triangle. $\endgroup$
    – user125315
    Feb 18, 2014 at 11:48
  • $\begingroup$ Sorry, you start with a triangle and add an edge to every vertex of degree one? $\endgroup$ Feb 18, 2014 at 18:04
  • $\begingroup$ Yeah, that needed to be 'two'. So you have a triangle, at every vertex you add an edge to some new vertex. Now you have a triangle, plus three leaves. For every vertex of degree one (the three new vertices) you add one triangle and identify one vertex of the first triangle with the first leaf, one vertex of the second triangle with the second leaf. Same for 'three'. $\endgroup$
    – user125315
    Feb 18, 2014 at 20:02
  • $\begingroup$ that's nice; can we say something about the induced subgraphs however? it pretty much looks like there's no other bad graphs $\endgroup$ Feb 19, 2014 at 6:18

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.