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

رنگ آمیزی کامل گراف. در نظریه گراف، رنگ آمیزی کامل گراف یک نوع از رنگ آمیزی یالها و راسهای گراف می باشد. اگر این نوع از رنگ آمیزی بدون هیچ شرط و قیدی بیان شود معمولاً اینگونه است که هیچ راسی، هیچ یال متلاقی و همچنین هیچ یال و رئوس دو سر آن یک رنگ نباشند.
عدد رنگی کامل ( χ ( G یک گراف حداقل تعداد رنگهای لازم برای رنگ آمیزی کامل یک گراف G است. گراف کامل T = T ( G ) گراف G یک گراف است با این شرایط: اولاً اینکه مجموعهٔ رئوس T متناظر باشند با رئوس و یالهای G و دوماً اینکه دو راس در T مجاورند اگر و فقط اگر عناصر متناظر آن ها در G یا مجاور باشند یا متلاقی.
برخی از خصوصیات عدد رنگی کامل  :
• χ″ ( G ) ≥ Δ ( G ) + ۱.
• χ″ ( G ) ≤ Δ ( G ) + ۱۰۲۶.
• χ″ ( G ) ≤ Δ ( G ) + ۸ ln۸ ( Δ ( G ) ) .
• χ″ ( G ) ≤ ch′ ( G ) + ۲.
در اینجا Δ ( G ) حداکثر درجهٔ گراف و ch′ ( 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 است. [ ۱]