The depth-first search tree structure of \(TK_{\aleph_ 0}\)-free graphs (Q1333343)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | The depth-first search tree structure of \(TK_{\aleph_ 0}\)-free graphs |
scientific article |
Statements
The depth-first search tree structure of \(TK_{\aleph_ 0}\)-free graphs (English)
0 references
13 September 1994
0 references
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.
0 references
infinite complete graph
0 references
spanning tree
0 references
depth-first search tree
0 references
finite tree-width
0 references
