Intuitively, a tangle of large order in a graph is a highly-connected part of the graph, and it is known that if a graph has a tangle of large order then it has a large grid minor. Here we show that for any k, if G has a tangle of large order and Z is a set of vertices of cardinality k that cannot be separated from the tangle by any separation of order less than k, then G has a large grid minor containing Z, in which the members of Z all belong to the outside of the grid.
Rooted grid minors / Marx, Daniel; Seymour, Paul; Wollan, Paul. - In: JOURNAL OF COMBINATORIAL THEORY. - ISSN 0095-8956. - STAMPA. - 122:January 2017(2017), pp. 428-437. [10.1016/j.jctb.2016.07.003]
Rooted grid minors
Wollan, Paul
2017
Abstract
Intuitively, a tangle of large order in a graph is a highly-connected part of the graph, and it is known that if a graph has a tangle of large order then it has a large grid minor. Here we show that for any k, if G has a tangle of large order and Z is a set of vertices of cardinality k that cannot be separated from the tangle by any separation of order less than k, then G has a large grid minor containing Z, in which the members of Z all belong to the outside of the grid.| File | Dimensione | Formato | |
|---|---|---|---|
|
Wollan_Rooted_2017.pdf
accesso aperto
Tipologia:
Documento in Post-print (versione successiva alla peer review e accettata per la pubblicazione)
Licenza:
Creative commons
Dimensione
101.19 kB
Formato
Adobe PDF
|
101.19 kB | Adobe PDF |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
