قضیه بروکس

برای هر گراف بدون جهت همبند G با بیشترین درجه Δ، عدد رنگی G حداکثر Δ است مگر در حالتی که G خوشه یا دور فرد باشد، در این حالت عددرنگی Δ + ۱ است.

László Lovász یک اثبات ساده شده برای قضیه بروکس ارائه داد. اگر گراف دوهمبند نباشد مؤلفه‌های دوهمبند آن را می‌توان به صورت جدا رنگ‌آمیزی کرد و سپس رنگ‌آمیزی‌ها را با هم ترکیب کرد. اگر گراف یک راس v با درجهٔ کمتر از Δ داشته باشد، آنگاه یک الگوریتم رنگ‌آمیزی حریصانه که راس‌های دور از v را قبل از راس‌های مجاور آن رنگ می‌کند حداکثر Δ رنگ استفاده می‌کند. ازاین‌رو، سخت‌ترین حالت اثبات به گراف‌های Δ-منتظم دوهمبند با Δ≥۳ مربوط است. در این حالت، Lovász نشان داد که می‌توان یک درخت پوشا پیدا کرد به طوری که دو راس همسایه با ریشه v, u و w که با هم مجاور نیستند در درخت برگ باشند. یک رنگ‌آمیزی حریصانه از راس u و w شروع می‌کند و راس‌های باقی‌مانده از درخت پوشا را از پایین به بالا با حداکثر Δ رنگ، رنگ می‌کند. برای رنگ کردن هر راس به جز v، آن راس یک پدر در درخت دارد که هنوز رنگ نشده‌است، پس همسایه‌های رنگ شده این راس نمی‌توانند همهٔ رنگ‌ها را استفاده کرده باشند، در حالی که برای راس v هم دو راس همسایه آن، u و w رنگ یکسان دارند پس باز هم یک رنگ برای راس v باقی می‌ماند.

یک تعریف عمومی‌تر از این تئوری به فهرست رنگ‌آمیزی اشاره می‌کند: برای هر گراف هم‌بند بدون جهت با بیش‌ترین درجه Δ که خوشه یا دور فرد نباشد، و یک فهرست از Δ رنگ برای هر راس، می‌توان به هر راس یک رنگ از این فهرست تخصیص داد به صورتی که هیچ دو راس همسایه، رنگ یکسان نداشته باشند. به عبارت دیگر، فهرست تعداد رنگ گراف هم‌یند بدون جهت G هرگز از Δ بیش‌تر نمی‌شود، مگر G خوشه یا دور فرد باشد. این قضیه توسط Vadim Vizing اثبات شده‌است.

برای گراف‌های خاص، حتی کمتر از Δ رنگ نیاز است. Bruce Reed نشان می‌دهد Δ – ۱ رنگ کافی است اگر و فقط اگر گراف داده شده هیچ Δ-خوشه نداشته باشد، Δ ارائه شده به اندازه کافی بزرگ است. برای گراف‌های بدون مثلث، یا به صورت کلی‌تر گراف‌هایی که همسایگی هر راسش به اندازه کافی متراکم باشد، (O(Δ/log Δ رنگ کافی است.

درجه یک گراف در انواع دیگر رنگ‌آمیزی به صورت کران بالا نشان داده می‌شود: برای رنگ‌آمیزی یال، قضیه ویزینگ نتیجه می‌دهد که حداکثر Δ + ۱ رنگ لازم است. یک تعمیم از قضیه بروکس برای رنگ‌آمیزی کامل، که بیان می‌کند عدد رنگی کلی حداکثر Δ + ۲ است، توسط Behzad و Vizing حدس زده شده‌است. تئوری Hajnal–Szemerédi در رنگ‌آمیزی عادلانه بیان می‌کند هر گراف یک (Δ + ۱)-رنگ‌آمیزی دارد که در آن اندازه هر کلاس دو رنگ حداکثر یک اختلاف دارد.

یک Δ-رنگ‌آمیزی، یا حتی یک Δ-رنگ‌آمیزی فهرستی از یک گراف Δ-درجه‌ای ممکن است در زمان خطی پیدا شود. همچنین الگوریتم‌های کارآمدی برای پیدا کردن رنگ‌آمیزی بروکس در مدل‌های موازی و توزیع شدهٔ محاسبات وجود دارند.