Similar to star-comb lemma but finite graphs

208 Views Asked by At

The famous star-comb lemma for infinite graphs states that if $S$ is a infinite set of vertices in a connected graph $G$, then $G$ contains either a comb with all teeth in $S$ or a subdivision of an infinite star with all leaves in $S$.

Here by comb I mean a graph that is a path with an additional leaf joined to each vertex of the path and by teeth I mean the leaves of the comb. A star is a complete bipartite $K_{1,\mathbb{N}}$.

I would like a theorem of the same kind that gives an unavoidable (induced) subgraph (or subdivision of a subgraph) for a finite graph $G$ that contains a large star (a graph $K_{1,n}$ with $n$ big) as a minor, but contains a big comb (the order of the comb is given by the length of the main path). In other words, $G$ has a large star minor but bounded maximum degree.

Thanks!

1

There are 1 best solutions below

7
On

I'm not totally sure what you are looking for, but this result might be useful:

For any positive integer $r$, there is a positive integer $n$ so that any connected graph of order at least $n$ contains either $K_r$, $K_{1,r}$ or $P_r$ as an induced subgraph.

This is easy enough to prove, and is Proposition 9.4.1 in Diestel. Of course if you relax to subgraphs, an easy corollary is that in a large enough graph you can find either a large star or a large path subgraph.

There are similar results for unavoidable topological minors of large 2-connected graphs, and unavoidable minors of large 3-connected, internally 4-connected, and 4-connected graphs.