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

رنگ آمیزی کامل گراف. در نظریه گراف، رنگ آمیزی کامل گراف یک نوع از رنگ آمیزی یالها و راسهای گراف می باشد. اگر این نوع از رنگ آمیزی بدون هیچ شرط و قیدی بیان شود معمولاً اینگونه است که هیچ راسی، هیچ یال متلاقی و همچنین هیچ یال و رئوس دو سر آن یک رنگ نباشند.
عدد رنگی کامل (χ(G یک گراف حداقل تعداد رنگهای لازم برای رنگ آمیزی کامل یک گراف G است.گراف کامل T = T(G) گراف G یک گراف است با این شرایط: اولاً اینکه مجموعهٔ رئوس T متناظر باشند با رئوس و یالهای G و دوماً اینکه دو راس در T مجاورند اگر و فقط اگر عناصر متناظر آن ها در G یا مجاور باشند یا متلاقی.
برخی از خصوصیات عدد رنگی کامل :
در اینجا Δ(G) حداکثر درجهٔ گراف و ch′(G) توانایی انتخاب یالها هستند.