رنگ‌آمیزی کامل گراف

χ″(G) ≤ Δ(G) + ۲.

اصطلاح «رنگ آمیزی کامل» و عبارت «حدس رنگ آمیزی کامل» در موقعیت‌های زیادی (در سال‌های ۱۹۶۴ و ۱۹۶۸) توسط بهزاد و وایزینگ به‌طور مستقل مورد استفاده قرار گرفته‌است. حدس رنگ آمیزی کامل فقط برای دستهٔ کوچک ولی مهمی از گرافها مثل تمام گرافهای دوبخشی و اکثر گرافهای مسطح به جز آنهایی که دارای حداکثر درجهٔ ۶ هستند؛ برقرار می‌باشد. اگر 'حدس گراف مسطح وایزینگ' درست باشد رنگ آمیزی کامل تمام گرافهای مسطح را دربر خواهد گرفت.

این قضیه (وایزینگ) برای همه گرافهای بدون طوقه معتبر است تعداد ماکسیمم یالهایی که دو راس G را به هم متصل می‌کنند چندگانگی G می‌نامند و ان را با (G)µ نشان می‌دهند. اکنون می‌توانیم قضیه وایزینگ را در حالتی کاملاً بیان کنیم : اگر G بدون طوقه باشد انگاه ∆ + µ ≤ ׳x ∆ ≤ این قضیه بدین معنا بهترین است که برای هر µ گراف G موجود است به‌طوری‌که ∆ + µ = ׳x

برهان : فرض کنید G گرافی ساده‌است. تنها لازم است که نشان دهیم x′ ≤ ∆ + 1 در این صورت، فرض کنید که، .x′>∆+1 فرض کنید که ϐ = (E1,E2,..., ∆+1E) (1+∆)-رنگ امیزی یالی اپتیمالG بوده و u راسی باشد به‌طوری‌که d(u)>c(u) د این صورت رنگهای i0,i1 وجود دارند که i0 در u ارائه نشده وi1 حداقل دو بار در u ارائه شده‌است. فرض کنید uv1، دارای رنگ i1 باشد. چون∆+1>d(v1)، رنگی مانند i2 در v1 ارائه نشده‌است.اکنون i2 باید در u ارائه شود، زیرا در غیر این صورت، با رنگ امیزی دوباره uv1 با i2، اصلاحی برای ϐ به دست می‌آوریم. لذا یالی مانندuv1 دارای رنگi2 است. دوباره، چون ∆+1>d(v2)، رنگی مانند i3 در v2 ارائه نشده وi3 باید در u ارائه شود زیرا در غیر این صورت، با رنگ امیزی دوبارهuv1 با i3 وuv2 باi3، یک(∆+1)-رنگ امیزی یالی اصلاح شد را به دست می‌آوریم. لذا یالی مانند uv3 دارای رنگ i3 است. با ادامه این شیوه، دنبالهٔ v1,v2,... از راسها و دنباله i1,i2,... از رنگها را می‌سازیم، به‌طوری‌که UVi دارای رنگ Ij و +1Ij درVi ارائه نشده‌است. چون درجه u متناهی است، کوچکترین عدد صحیح l ی وجود دارد به‌طوری‌که برای مقداری از k با شرط l>kو 1+jI= k این وضعیت در شکل الف رسم شده‌است. اکنون G را به ترتیب زیر دو بار رنگ می کنیم. برای(j≤1,j≥ k−1)، UVj را با رنگ1 +jI دوباره رنگ می‌کنیم، (∆+1)رنگ امیزی یالی جدید(e1,e2,...,∆ +1e) = ׳ϐ به دست می‌اید. به وضوح c′(v) ≥ c(v) و بنابراین ׳ϐ هم یک(∆+1)رنگ امیزی یالی اپتیمال از G است. مؤلفه ׳H از (ei U eik)G که شامل u است یک دور فرد است. حال علاوه بر این UVj را با رنگL−1 ≤J K≤را با رنگ Ik دوباره رنگ می‌کنیم، تا (∆+1)رنگ امیزی یالی (׳e1,..., ∆+1׳e) =׳׳ϐ به دست می‌اید (v)c ≥ (v)׳׳c و مؤلفه׳׳H از(׳ei U ׳eik)G که شامل u است یک دور فرد است. اما چونVk دارای درجهٔ دو در ׳H است، به وضوح Vk دارای درجهٔ یک در ׳׳H است.

رنگ‌آمیزی یالیk: رنگ امیزی یالی ϐاز گراف بدون طوقه G تخصیص k رنگ 3,2,1,...k به یالهای G است.

رنگ امیزی سره: رنگ امیزی ϐ سره‌است اگر هیچ دو یال مجاور همرنگ نباشند.

متقابلاً K-رنگ امیزی یالی را می‌توان به صورت یک افراز (E1,E2,...,Ek) از E تصور کرد، که در ان Ei زیرمجموعه‌ای (احتمالاً خالی) از E را نشان می‌دهد که رنگ i را اختیار کرده‌است. پس k-رنگ امیزی یالی سره، k-رنگ امیزی یالی (E1, E2,...,Ek) است که در ان هر زیرمجموعهٔ Ei یک جورسازی است.

قضیه: اگرG دوبخشی باشد آنگاه x′ = ∆.

برهان : فرض کنید G گرافی با x′> ∆ باشد، گیریم(∆E1, E2,..., E)= ϐ یک ∆-رنگ امیزی یالی اپتیمال از G است، و u راسی است که برای ان d(u)>c(u). بنابراین G شامل یک دور فرد بوده و لذا دو بخشی نیست. نتیجه می‌شود که اگر G دوبخشی باشد انگاهx′ = ∆.‏

مسئله جدول زمانی

در یک مدرسه، m معلم X1,X2,...,Xm و n کلاس Y1,Y2,...,Yn وجود دارند. اگر بدانیم از معلمXi خواسته شده‌است که در کلاس Yj برای دوره‌های Pij تدریس کند، جدول زمانی کاملی را با مینیمم تعداد دوره‌های ممکن برنامه‌ریزی کنید. این مسئله به مسئله جدول زمانی مشهور است، و می‌توان ان را کاملاً با استفاده از نظریهٔ رنگ امیزی یالی حل کرد. ما نیازهای اموزشی را به وسیله گراف دو بخشی G با بخش‌های (x,y) معرفی کنیم، که در ان X =(x1,...,xm) و (y1,...,yn)=Y و راسهای Xi و Yj به وسیله یالهای pij به هم متصل می‌شوند. اکنون در هر دوره، یک معلم حداکثر در یک کلاس می‌تواند تدریس کند. و تدریس در هر کلاس به وسیلهٔ حداکثر یک معلم می‌تواند انجام شود این، حداقل، پذیره ماست. لذا برنامه‌ریزی اموزشی برای یک دوره متناظر با جورسازی در گراف است و، بر عکس، هر جورسازی، متناظر با تخصیصی ممکن از معلمان به کلاسها برای یک دورا است. بنابراین، مسئلهٔ ما افرازهای یالهای G به کمترین جورسازی‌های ممکن، یا هم ارز ان، رنگ امیزی مناسب یالهای G با کمترین رنگ ممکن است. چون G دوبخشی است، می‌دانیم که x′ = ∆ لذا اگر هیچ معلمی برای بیش از p دوره درس ندهد، و اگر در هیچ کلاسی برای بیش ازp یوره تدریس نشود. نیازهای اموزشی را می‌توان در جدول زمانی p-دوره‌ای برنامه‌ریزی کرد.

در عمل بیشتر مسایل مربوط به جدول زمانی با تخصیص پیشین مسایلی مشکل‌اند. این تعمیم مسئله جدول زمانی را دمپستر(1971)و دوورا(1970)مطالعه کرده‌اند.