Graph Theory: 66. Basic Bound on the Chromatic Number
In this video we prove by induction that every graph has chromatic number at most one more than the maximum degree. Odd cycles and complete graphs are examples for which the chromatic number meets this upper bound exactly. For other graphs, Brook's Theorem tells us that the chromatic number is at most the maximum degree. We will prove Brook's Theorem in a later video.
-- Bits of Graph Theory by Dr. Sarada Herke.
Related videos:
• Graph Theory: 64. Vertex Colouring - Graph Theory: 64. Vertex Colouring
• Graph Theory: 65. 2-Chromatic Graphs - Graph Theory: 65. 2-Chromatic Graphs