رنگ امیزی فهرستی گراف

رنگ آمیزی فهرستی گراف. در نظریه گراف، که شاخه ای از ریاضیات است، رنگ آمیزی لیستی نوعی از رنگ آمیزی گراف است. در این رنگ آمیزی برای هرراس لیستی از رنگ ها وجود دارد که آن راس می تواند توسط یکی از رنگ های این لیست رنگ شود. این شاخه ابتدا توسط ویزینگ[ ۱] ( به انگلیسی: Vising ) ، اردوش ( به انگلیسی: Erdős ) ، رابین ( به انگلیسی: Rubin ) و تیلور ( به انگلیسی: Taylor ) [ ۲] [ ۳] [ ۴] مورد مطالعه قرار گرفت و بنیان آن بنا شد.
G را یک گراف در نظر بگیرید و برای هر راس مانند v از گراف، ( L ( v را لیستی از رنگ های موجود برای آن رأس، تعریف کنید. رنگ آمیزی لیستی یک رنگ آمیزی انتخابی است که به هر راس مانند v یک رنگ دلخواه از لیست رنگ های آن راس ( ( L ( v ) متناظر می کند. به یک رنگ آمیزی لیستی خوب می گوییم هرگاه هیچ دو راس مجاوری همرنگ نباشند. یک گراف را k - لیست رنگ پذیر می نامیم هرگاه مستقل از این که لیست k رنگیِ رنگ های هر راس چیست، یک رنگ آمیزی لیستی خوب برای آن وجود داشته باشد. عدد رنگی لیستی ( ( ch ( G ) گراف G، کوچکترین عدد k است که گراف k، G رنگ پذیر است.
به بیان دقیق تری، برای یک تابع مانند f که به هر راس مانند v یک عدد صحیح مثبت، ( f ( v را نسبت می دهد، گراف G را f - لیست رنگ پذیر می نامند، هرگاه مستقل از این که لیست ( f ( v رنگیِ هر راس مانند v شامل چه رنگ هایی باشد، یک رنگ آمیزی لیستی خوب برای آن وجود داشته باشد. به طور خاص اگر برای هر راس مانند f ( v ) = k ، v باشد، گراف k - لیست رنگ پذیر می باشد.
فرض کنید q یک عدد صحیح مثبت باشد و G یک گراف کامل دوبخشی Kq, qq باشد. رنگ های موجود را با q2 عدد دو رقمی مختلف در مبنای q نمایش می دهیم. در بخشی از این گراف دو بخشی که q راس دارد، هر راس از گراف را متناظر با مجموعه ای از رنگ ها در نظر می گیریم که رقم باارزش آن ها یکسان است. برای مثال به راس شمارهٔ i ام مجموعه رنگ های {i0, i1, … , iq} متناظر می کنیم. در بخش دیگر از این گراف دو بخشی، به هر راس از qq راس این گراف یک مجموعه از رنگ ها مانند {. . . , 0a, 1b, 2c}، به طوری که رقم باارزش آن ها متفاوت باشد. به تعداد qq تا مجموعه با چنین خاصیتی وجود دارد، زیرا تعداد q - تایی های ( . . . , a, b, c ) برابر با qq است. برای مثال اگر q = 2 باشد، گراف دو بخشی K2, 4 خواهیم داشت. در این گراف دو راس واقع در یک بخش این گراف مجموعه رنگ های {00, 01}, {10, 11} و 4 راس واقع در بخش دیگر گراف مجموعه رنگ های {00, 10}, {00, 11}, {01, 10}, {01, 11} را دارند. تصویر روبرو یک مثال بزرگ تر را به ازای q = 3 نشان می دهد.