The colour lemma. A combinatorial result and its application to tree partitions (Q2763619)

Aus dem Vorwort des Autors: Das Farbenlemma ist das wesentliche Resultat im ersten Abschnitt dieser Arbeit: Es sagt, dass Bäume, deren Knoten mit endlich vielen Farben gefärbt wurden, Teilbäume enthalten, die in gewissem Sinne ``monochrom'' sind. Eine weitere strukturelle Eigenschaft von Bäumen wird am Ende des ersten Abschnitts durch das I-H-Lemma beschrieben.NEWLINENEWLINENEWLINEIm zweiten Teil können wir ein von Paul Seymour formuliertes Problem positiv beantworten. Es sei \(P\) ein außenplanarer Graph und es sei \(Q\) ein Graph mit einem Knoten \(v\), so dass \(Q\setminus v\) ein Baum ist. Dann existiert eine nur von \(P\) und \(Q\) abhängige Konstante \(K\), so dass jeder zweizusammenhängende Graph mit Pfadweite größer als \(K\) einen der Graphen \(P\) oder \(Q\) als Minor enthält.NEWLINENEWLINENEWLINEDieses Theorem verallgemeinert ein Resultat aus Robertsons and Seymours Serie über Graphenminoren. In seinem Beweis werden die Ergebnisse aus Teil I auf Bäume in Baumzerlegungen angewendet, wobei das Farbenlemma in wiederholten Anwendungen die zentrale Rolle spielt. Einige Überlegungen, under anderem der Beweis von Proposition 9.3, erfolgten gemeinsam mit Professor Thomas.NEWLINENEWLINENEWLINEIm dritten Teil streifen wir zwei Aspekte, die in einem Zusammenhang mit dem Farbenlemma und dem bewiesenen Theorem stehen: Wir werfen einen Blick auf die formale Ähnlichkeit des Farbenlemmas mit ramseyartigen Resultaten, und wir betrachten kurz den Zusammenhang des Theorems mit der Matroidtheorie.