Abstract
In a series of four papers we determine structures whose existence is dual, in the sense of complementary, to the existence of stars or combs from the well-known star—comb lemma for infinite graphs. Call a set U of vertices in a graph G tough in G if only finitely many components of G − X meet U for every finite vertex set X ⊆ V (G). In this fourth and final paper of the series, we structurally characterise the connected graphs G in which a given vertex set U ⊆ V (G) is tough. Our characterisations are phrased in terms of tree-decompositions, tangle-distinguishing separators and tough subgraphs (a graph G is tough if its vertex set is tough in G). From the perspective of stars and combs, we thereby find structures whose existence is complementary to the existence of so-called undominating stars.
Original language | English |
---|---|
Pages (from-to) | 140-162 |
Number of pages | 23 |
Journal | Journal of Graph Theory |
Volume | 100 |
Issue number | 1 |
Early online date | 17 Jan 2022 |
DOIs | |
Publication status | Published - May 2022 |
Keywords
- complementary
- critical vertex set
- dual
- duality
- infinite graph
- star comb lemma
- star decomposition
- tough vertex set
- tree set
- undominating star