Brooks' theorem

GPTKB entity

Statements (14)
Predicate Object
gptkbp:instanceOf gptkb:mathematical_concept
gptkbp:appliesTo connected undirected graphs
gptkbp:author gptkb:R._L._Brooks
gptkbp:chromaticNumberBound maximum degree
gptkbp:excludes complete graphs
odd cycles
gptkbp:field graph theory
https://www.w3.org/2000/01/rdf-schema#label Brooks' theorem
gptkbp:namedAfter gptkb:R._L._Brooks
gptkbp:publishedIn gptkb:Mathematical_Proceedings_of_the_Cambridge_Philosophical_Society
gptkbp:sentence In a connected undirected graph, the chromatic number is at most the maximum degree, unless the graph is a complete graph or an odd cycle.
gptkbp:yearProved 1941
gptkbp:bfsParent gptkb:Graph_coloring_problem
gptkbp:bfsLayer 6