ادامه رنگ آمیزی نمودار
سایر رنگها [ ویرایش ]
نظریه رمزی [ ویرایش ]
مقاله اصلی: نظریه رمزی
کلاس مهمی از مشکلات نادرست در رنگ آمیزی در نظریه رمزی ، که لبه های نمودار به رنگ ها اختصاص داده شده است ، مورد مطالعه قرار می گیرد و محدودیتی در رنگ لبه های حادثه دیده نمی شود. یک مثال ساده ، قضیه دوستی است ، که بیان می کند در هر رنگ آمیزی از لبه های
سایر رنگها [ ویرایش ]
رنگ مجاور- vertex- مشخص کننده کل یک رنگ کلی با محدودیت اضافی که هر دو راس مجاور دارای مجموعه های مختلف رنگ هستند هر زیرگراف 2-کرومیک غیرقانونی است رنگ آمیزی راسهایی که در آن هر کلاس رنگ دارای یک راس است که در همه کلاسهای رنگ دیگر همسایه دارد. با انگیزه سیستم های وظیفه ای که در آن تولید به روش چرخشی انجام می شود یک رنگ آمیزی صحیح راس که در آن هر کلاس رنگ باعث ایجاد یک مجموعه مستقل یا یک کلیشه می شود هر جفت رنگ حداقل در یک لبه ظاهر می شود رنگ آمیزی نامناسب ورته که در آن هر کلاس رنگ باعث ایجاد یک زیرگراف درجه محدود می شود. یک نقوش راس نادرست که همه تقارن های نمودار را از بین می برد اندازه کلاس رنگ حداکثر یک متفاوت است هر جفت رنگ دقیقاً در یک لبه ظاهر می شود گرتك ها ممكن است دارای چندین رنگ باشند و در هر لبه تعداد قسمت های رنگی هر راس از یكدیگر بیشتر نیست از طول طولانی ترین مسیر بین دو راس ، که به عنوان فاصله دوری نیز شناخته می شود ، استفاده می کند هر جفت رنگ حداکثر در یک لبه ظاهر می شود هر بروز مجاور ورت و لبه با رنگهای مشخصی رنگ آمیزی می شود رنگ لبه هایی که در یک راس مشترک قرار دارند ، باید متناقض باشد هر راس از لیست رنگ ها انتخاب می کند هر لبه از لیست رنگ ها انتخاب می کند تفاوت رنگها در راسهای مجاور حداقل h و تفاوت رنگهای رئوس در فاصله دو حداقل k است . مورد خاص ، رنگ L (2،1) است .
جهت گیری لبه های نمودار را در نظر می گیرد یک مشکل مسیریابی را در نمودارها مدل می کند مجموع فاصله بین رئوس ها و تفاوت رنگ آنها از k + 1 بیشتر است ، در جایی که k عدد صحیح مثبت است. اگر دو رأس دارای یک رنگ i مشابه باشند ، پس هر مسیری بین آنها دارای یک راس با رنگ بیشتر از من است رنگ آمیزی نامناسب ورته که در آن هر کلاس رنگ باعث ایجاد اتحادیه کلیشه ها می شود ملاک به حداقل رساندن جمع رنگها است هر زیرگرافی 2-کروماتیک مجموعه ای جدا از ستاره است هر رنگ دقیقاً یک بار در هر پارتیشن با اندازه مساوی ظاهر می شود لبه ها به گونه ای رنگ شده اند که هر کلاس رنگ تطبیق را ایجاد می کند (معادل رنگ آمیزی مربع نمودار خط) مقدار مطلق تفاوت بین دو رنگ راسهای مجاور نباید به مجموعه ثابت T تعلق داشته باشد گره ها و لبه ها رنگی هستند هر زیرگراف القایی متصل دارای رنگی است که دقیقا یکبار استفاده می شود لبه ها به گونه ای رنگ شده اند که هر کلاس رنگ یک زیرگراف عاری از مثلث تشکیل می دهد یک نقوش راس نادرست که در آن هر گره غیر منزوی حداقل یک همسایه با رنگ متفاوت دارد
|
همچنین می توان رنگ آمیزی را برای نمودارهای امضا شده در نظر گرفت و نمودارهایی را بدست آورد .
منبع