The depth-first search tree structure of \(TK_{\aleph_ 0}\)-free graphs
type: Item
instance of: scholarly article
title: The depth-first search tree structure of \(TK_{\aleph_ 0}\)-free graphs
zbMATH Open document ID: 0809.05079
author: Reinhard Diestel
published in: Journal of Combinatorial Theory. Series B
publication date: 1994-09-13T00:00:00Z
review text: The note proves that the following two assertions are equivalent for connected graphs \(G\): (i) \(G\) contains no subdivided infinite complete graph as a subgraph; (ii) \(G\) has a normal spanning tree, that means a depth-first search tree, such that any ray in \(T\) has only finitely many neighbours. This implies a result of Robertson, Seymour and Thomas that these are precisely the graphs of finite tree-width.
Mathematics Subject Classification ID: 05C75
Mathematics Subject Classification ID: 05C05
zbMATH DE Number: 638664
zbMATH Keywords: infinite complete graph
zbMATH Keywords: spanning tree
zbMATH Keywords: depth-first search tree
zbMATH Keywords: finite tree-width
reviewed by: Dietmar Cieslik
MaRDI profile type: Publication
full work available at URL: jctb.1994.1048
OpenAlex ID: W1970364030
DOI: 10.1006/JCTB.1994.1048
description: scientific article; zbMATH DE number 638664