No label defined (Q4027183)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 125481
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 125481 |
Statements
21 February 1993
0 references
Brooks' theorem
0 references
\(k\)-colorability
0 references
forbidden subtree
0 references
0 references
0 references
0 references
0 references
0 references
[For the entire collection see Zbl 0748.00023.] It was shown in \textit{R. L. Brooks} [Proc. Camb. Philos. Soc. 37, 194-197 (1941; Zbl 0027.26403)] that if a connected graph \(G\) does not contain \(K_{1,k+1}\), \(k\geq 3\), then \(G\) is \(k\)-colorable unless \(G=K_{k+1}\). The paper under review generalizes this result by replacing the star \(K_{1,k+1}\) by an arbitrary tree with \(k+2\) vertices.
0 references