قضیه بروکس

در نظریهٔ گراف، قضیه بروکس (به انگلیسی: Brooks' theorem) رابطه‌ای بین بیشترین درجه یک گراف و عدد رنگی آن بیان می‌کند. بر اساس این قضیه، در یک گراف همبند که هر راسی حداکثر Δ همسایه دارد، راس‌ها می‌توانند تنها با Δ رنگ، رنگ آمیزی شوند، به جز در دو حالت، گراف‌های کامل و گراف‌های دوری با دور به طول فرد، که به Δ + ۱ رنگ نیاز دارند.

گراف‌های کامل به یک رنگ بیشتر از بیشترین درجه‌شان نیاز دارند. این گراف‌ها و گراف‌های دوری با دور فرد تنها استثنائات قضیه بروکس هستند.

این قضیه به افتخار R. Leonard Brooks نام‌گذاری شده‌است، کسی که یک اثبات از این مسئله را در سال ۱۹۴۱ منتشر کرد. یک رنگ‌آمیزی با تعداد رنگ‌هایی که قضیه بروکس ارائه می‌دهد، عموماً رنگ‌آمیزی بروکس یا Δ-رنگ‌آمیزی نامیده می‌شود

گزاره رسمی

برای هر گراف بدون جهت همبند 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 Δ رنگ کافی است.[1]

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

الگوریتم

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

یادداشت
  1. Alon, Krivalevich & Sudakov (1999).
  2. Skulrattanakulchai (2006).
  3. Karloff (1989); Hajnal & Szemerédi (1990); Panconesi & Srinivasan (1995); Grable & Panconesi (1998).

منابع

    پیوند به بیرون
    • Weisstein, Eric W. "Brooks' Theorem". MathWorld.
    This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.