JavaScript is disabled for your browser. Some features of this site may not work without it.
A Generalization of Brooks' Theorem

Author
Srinivasan, Aravind
Abstract
Given a connected graph $G = (V, E)$ with $n$ vertices and maximum degree $\Delta$ such that $\Delta \geq$ 3 and $G$ is not a complete graph, Brooks' theorem shows that $G$ is $\Delta$-colorable. We prove a generalization of this theorem: assume inductively that all but one vertex $v$ is colored; then, $v$ can be colored by considering the vertices (and their colors) in just an $O$ (log $n$) radius around $v$. Our proof uses a probabilistic technique to link the connectivity and diameter of "almost-regular" graphs, which could have other applications too.
Date Issued
1992-09Publisher
Cornell University
Subject
computer science; technical report
Previously Published As
http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR92-1302
Type
technical report