scientific article; zbMATH DE number 125481
From MaRDI portal
Publication:4027183
[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.
Recommendations
- Brooks' Theorem and Beyond
- An Extension of Muchnik's Theorem
- scientific article; zbMATH DE number 4214785
- An extension of Behrend's theorem
- Yet another proof of Brooks' theorem
- Brook's theorem
- An extension of Pohlmeyer's theorem
- scientific article; zbMATH DE number 4075598
- scientific article; zbMATH DE number 4040368
Cited in
(6)- An NC algorithm for Brooks' theorem
- A characterisation of some 2-connected graphs and a comment on an algorithmic proof of Brooks' theorem
- A reconfigurations analogue of Brooks' theorem and its consequences
- A fractional analogue of Brooks' theorem
- Brooks' Theorem and Beyond
- Brooks' theorem for generalized dart graphs
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4027183)