Title of article :
Highly Connected Sets and the Excluded Grid Theorem
Author/Authors :
Diestel، نويسنده , , Reinhard and Jensen، نويسنده , , Tommy R. and Gorbunov، نويسنده , , Konstantin Yu. and Thomassen، نويسنده , , Carsten، نويسنده ,
Issue Information :
روزنامه با شماره پیاپی سال 1999
Abstract :
We present a short proof of the excluded grid theorem of Robertson and Seymour, the fact that a graph has no large grid minor if and only if it has small tree-width. We further propose a very simple obstruction to small tree-width inspired by that proof, showing that a graph has small tree-width if and only if it contains no large highly connected set of vertices.
Journal title :
Journal of Combinatorial Theory Series B
Journal title :
Journal of Combinatorial Theory Series B