Excluding infinite minors (Q1191928): Difference between revisions

Graphs are considered which may be infinite and they may have loops or multiple edges. In former articles the authors have shown that for any infinite sequence \(G_ 1,G_ 2,\dots\) of finite graphs there exist \(j>i\geq 1\) such that \(G_ i\) is isomorphic to a minor of \(G_ j\). But in the case that the graphs of the sequence are uncountable the result above fails. The following investigations for a sequence of countable graphs were unsuccessful. But the authors discovered a great number of new decomposition theorems for infinite graphs and they observerd that graphs without so-called \(H\)-minors play a deciding role. Precisely, let \(\kappa\) be an infinite cardinal and let \(H\) be either a complete graph \(K_ \kappa\) with \(\kappa\) vertices, or a tree \(T_ \kappa\) in which every vertex has valency \(\kappa\); they investigated such graphs which have no minor isomorphic to \(H\) \((H\)-minor) or which contain no subgraph which is a subdivision of \(H\). In this paper these problems are answered for each infinite cardinal \(\kappa\). There is a connection between the structure of graphs not containing \(T_ \kappa\) and a cops-and-robber game played on a graph, where \(<\kappa\) cops try to corner a robber. It turns out, for \(\kappa\) uncountable, that the robber can survive iff the graph has a \(T_ \kappa\)-minor; and there is a particularly simple kind of survival strategy iff there is a \(K_ \kappa\)-minor. These connections with minors are described and investigated in section 2 of the paper and in section 3 there is observed that the non-existence of the survival strategy of escaping is equivalent with the existence of a certain kind of decomposition of the graph. And different decompositions are defined and described in the following chapters. The case of excluding the \(K_ \kappa\)-minors for \(\kappa=\aleph_ 0\) which till now could not be treated is discussed in section 7. The very many results are comprehensively summarized in section 8. As an example at least one result (8.4) may given now (without definitions of some here mentioned concepts): For all \(\kappa>\aleph_ 0\) the following are equivalent: \(G\) has no \(T_ \kappa\)-minor, less than \(\kappa\) cops can search \(G\), \(G\) has a rayless three-decomposition of width \(<\kappa\), \(G\) has a scattered tree-decomposition of width \(<\kappa\) and adhesion \(<\kappa\), \(G\) has a well-ordered decomposition of width \(<\kappa\) and adhesion \(<\kappa\), \(G\) has a scattered linear decomposition of width \(<\kappa\) and adhesion \(<\kappa\).