Payamvdn/NorthPersian_fa_wiki huggingface dataset:
ستند که عمدتاً در جده ساکن هستند. زبان ها. زبان رسمی عربستان سعودی، عربی است. گویش اصلی منطقه ای استان مکه که توسط سعودی ها صحبت می شود، عربی حجازی است و اقلیتی از گویشوران عربی نجدی در بخش های شرقی منطقه وجود دارند. زبان اشاره سعودی زبان اصلی جامعه ناشنوایان است. جوامع بزرگ مهاجر نیز به زبان های خود صحبت می کنند که از جمله آنها می توان به برخی از زبان های هندی، فیلیپینی/تاگالوگ، بنگالی و اردو اشاره کرد. آموزش. از ۱٬۸۲۳٬۵۹۸ نفر از ساکنان مرد سعودی بالای ۱۰ سال، ۸۷٫۵۷٪ (معادل ۱٬۵۹۶٬۹۴۶ نفر) به نوعی تحصیلات رسمی داشته اند، در حالی که ۲۲۶٬۶۵۲ نفر بی سواد بوده اند. در مورد زنان، از ۱٬۷۶۵٬۶۶۶ نفر ساکن بالای ۱۰ سال، ۷۷٫۲۸٪ یا ۱٬۳۶۴٬۵۲۹ نفر به طور رسمی تحصیل کرده اند، در حالی که ۴۰۱٬۱۳۷ نفر بی سواد بوده اند. بهداشت و درمان. از ساکنان سعودی استان که بالای ۱۵ سال سن داشته اند، ۱٫۱۵٪ در سال ۲۰۱۶ نوعی معلولیت را گزارش کرده اند که اختلال بینایی شایع ترین نوع معلولیت و پس از آن کاهش تحرک بوده است، در حالی که ۱۰۷٬۷۷۰ نفر معلولیت شدید یا بسیار شدید را گزارش کرده اند.
در نظریهٔ گراف، یک رنگ آمیزی یالی از یک گراف، نسبت دادن "رنگ ها" به یال های گراف است به نحوی که هیچ دو یال مجاوری رنگ یکسان نداشته باشند. برای مثال، تصویر سمت چپ نمایانگر یک رنگ آمیزی یالی از یک گراف با رنگ های قرمز، آبی، و سبز است. رنگ آمیزی یالی یکی از انواع مختلف رنگ آمیزی گراف است. مسئلهٔ رنگ آمیزی یالی بررسی می کند که آیا ممکن است یال های یک گراف داده شده را با حداکثر رنگ متفاوت که داده شده است، یا با کمترین تعداد رنگ ممکن، رنگ کرد. کمترین تعداد لازم رنگ برای یال های یک گراف داده شده، شاخص رنگی آن گراف نامیده می شود. برای مثال، گراف تصویر با سه رنگ، رنگ می شود ولی نمی توان آن را با دو رنگ رنگ کرد، پس شاخص رنگی آن سه است. بنابر قضیهٔ ویزینگ، تعداد رنگ های لازم برای رنگ آمیزی یالی یک گراف ساده برابر با بیشترین درجهٔ آن Δ یا Δ+۱ است. برای برخی از گراف ها مانند گراف های دوبخشی یا گراف های مسطح با درجهٔ بالا تعداد رنگ های لازم همیشه Δ است؛ ولی برای گراف های چندگانه تعداد رنگ های ممکن است به بزرگی ۳Δ/۲ باشد. الگوریتم هایی با زمان های چندجمله ای وجود دارند که رنگ آمیزی بهینهٔ گراف های دوبخشی یا گراف های غیر دوب
خشی ساده که حداکثر Δ+۱ رنگ لازم دارند را محاسبه می کند؛ در صورتی که مسئلهٔ کلی یافتن رنگ آمیزی بهینه ان پی کامل است و سریع ترین الگوریتم شناخته شده برای آن، زمان نمایی نیاز دارد. انواع دیگری از مسئلهٔ رنگ آمیزی یالی مطالعه شده اند که در آن ها نسبت دادن رنگ ها به یال ها باید شرایط دیگری غیر از نامجاور بودن را نیز برآورده کند. مسئلهٔ رنگ آمیزی گراف کاربردهایی در مسائل زمان بندی و نیز انتساب فرکانس برای شبکه های فیبرنوری دارد. مثال. گراف دوری با طول دور زوج به دو رنگ و با طول فرد به سه رنگ برای رنگ آمیزی یالی نیاز دارد. در این گراف ها، رنگ آمیزی یالی به صورت یک درمیان صورت می گیرد. در گراف کامل با زوج به رنگ نیاز داریم. رنگ آمیزی گراف کامل، حالت خاص (Baranyai’s theorem]] Soifer 2008]]) به شمار می رود که راه حل هندسی زیر را ارائه می دهد: نقطه در مرکز یک -ضلعی قرار دهید. به هر یال رأس مرکزی، رنگ متفاوتی را انتساب دهید. برای یال های دیگر رئوس نیز همین کار را با رعایت شروط رنگ آمیزی انجام دهید. درصورتی که فرد باشد، برای رنگ آمیزی یالی به رنگ نیاز داریم: هر رنگ برای یال قابل استفاده است که این تعداد یال، تعداد کل یال
هاست. یکی از مسائل متداول در رنگ آمیزی یالی، رنگ آمیزی گراف های فرد است. گرافی که در آن هر رأس دقیقاً به رأس دیگر یال دارد و به صورت نشان داده می شود. گراف Petersen حالتی خاص از این گراف هاست که در آن برابر ۳ باشد. گراف فرد با های ۳٬۴,۸ به رنگ و گراف فرد با های ۵٬۶,۷ به رنگ برای رنگ آمیزی نیاز دارد. مسئله پیدا کردن جدول بازی ها برای چندین تیم را در نظر بگیرید که در آن هر تیم می بایست با دیگر تیم ها بازی کند، هرتیم در یک روز حداکثر یک بازی انجام می دهد و بازی ها در ۶ روز هفته (به جز جمعه ها) می تواند انجام شود. این مسئله را می توان به صورت رنگ آمیزی گراف فرد با مدل کرد که (Biggs 1972) این مسئله را حل کرده است. تعریف. رنگ آمیزی یالی به انتساب رنگی مناسب به هر یال گفته می شود به صورتی که به هیچ دو یال مجاور، رنگ یکسانی منتسب نشود. در این تعریف دو یال مجاور به دو یالی گفته می شود که رأس مشترک داشته باشند. رنگ آمیزی یالیی گراف معادل رنگ آمیزی رئوس گراف خطی است. گراف خطی گرافی است که به ازای هر یال یک رأس دارد و یال های آن معادل جفت یال های مجاور در است. به رنگ آمیزی یالی با رنگ مختلف -رنگ آمیزی-یالی گفته می شود.
به گرافی که این گونه قابل رنگ آمیزی باشد -رنگ پذیر-یالی گفته می شود. کمترین تعداد رنگ برای رنگ آمیزی یالی یک گراف را شاخص رنگی یا عدد رنگی یال گراف می گویند و آن را با نشان می دهند. همچنین شاخص رنگی را گاهی با نماد نشان می دهند که اندیس ۱ نشان دهنده یک بُعدی بودن یال هاست. گرافی که که شاخص رنگی آن باشد را -شاخص-یالی می نامند. نکتهٔ قابل توجه در اینجا این است که شاخص رنگی با عدد رنگی متفاوت است. عدد رنگی کمترین تعداد رنگ ها برای رنگ آمیزی رئوس گراف است و با یا نشان داده می شود. در صورتی که ذکر نشود همه گراف ها را گراف ساده فرض می کنیم. در مقابل گراف ساده، گراف های چندگانه تعریف می شود که گرافی است که یال ها بتوانند ابتدا و انتهای یکسانی داشته باشند یعنی بین دو رأس چندین یال وجود داشته باشد یا گراف طوقه داشته باشد. در بسیاری از مسائل رنگ آمیزی یالی، الگوریتم ها برای گراف ساده و گراف چندگانه متفاوت خواهد بود و برای تبدیل راه حل های رنگ آمیزی گراف ساده به گراف چندگانه ملاحظات بسیاری مورد نیاز است. رابطه با تطابق. یک تطابق در گراف مجموعه ای از یال های نامجاور است؛ یک تطابق کامل یک تطابق است که یال های آن تمامی رأس
ها را پوشش داده باشند، و تطابق بیشینه تطابقی است که بیشینه یال های ممکن را داراست. در رنگ آمیزی یالی، مجموعه یال های دارای یک رنگ خاص باید نامجاور باشند پس تشکیل یک تطابق می دهند. بنابراین یک رنگ آمیزی درست، معادل افراز کردن گراف به تطابق های جدا از هم است. اگر اندازهٔ تطابق بیشینهٔ یک گراف کوچک باشد، آن گاه تعداد تطابق های لازم برای پوشاندن تمام یال های گراف زیاد است. به بیان رسمی تر، اگر یک گراف دارای یال باشد و حداکثر یال متعلق به یک تطابق بیشینه باشند، آن گاه هر رنگ آمیزی یالی گراف حداقل نیاز به رنگ متفاوت دارد. برای مثال، گراف ۱۶-رأسی در تصویر روبه رو یال دارد. در این گراف، تطابق کامل وجود ندارد زیرا اگر رأس وسط تطبیق داده شود، رأس های تطبیق داده نشده باقی مانده در سه مؤلفهٔ همبندی متفاوت با ۴، ۵، و ۵ رأس جای می گیرند و مؤلفه های با تعدادرأس فرد تطابق کامل نخواهند داشت. برای این گراف تطابق بیشینه ای با ۷ یال موجود است، پس . بنابراین، تعداد رنگ های لازم برای رنگ آمیزی یالی حداقل ۲۴/۷ خواهد بود و چون تعداد رنگ ها باید عدد درستی باشد، حداقل به ۴ رنگ نیاز است. برای یک گراف منظم از درجهٔ که تطابق کامل ندارد،
می توان از این کران پایین استفاده کرد و نشان داد حداقل رنگ نیاز است. به طور خاص، این گفته برای گراف های منظم با تعداد فردی رأس (مانند گراف های کامل فرد) درست است؛ برای این گراف ها، طبق لم دست دادن (hankshaking lemma)، باید عددی زوج باشد. اما نامساوی کاملاً شاخص رنگی هر گراف منظمی را توضیح نمی دهد، زیرا گراف های منظمی وجود دارند که تطابق کامل دارند اما -رنگ پذیر-یالی نیستند. برای مثال، گراف پترسن منظم است با یال و یال در تطابق کامل، ولی ۳-رنگ آمیزی-یالی ندارد. رابطه با درجه. قضیهٔ ویزینگ. عدد رنگی یالی یک گراف رابطهٔ نزدیکی با بیشینه درجهٔ آن گراف ، بیشترین تعداد ممکن یال مجاور به هر رأسی از آن گراف، دارد. واضحاً زیرا اگر یال متفاوت همگی به یک رأس برسند، آن گاه همهٔ آن ها باید رنگی متفاوت از دیگری داشته باشند و این امر هنگامی ممکن است که حداقل رنگ متمایز برای نسبت دادن به آن ها وجود داشته باشد. قضیهٔ ویزینگ (نامیده شده به خاطر ودیم جی ویزینگ که این قضیه را در ۱۹۶۴ اثبات و منتشر کرد) بیان می کند که این مرز تقریباً دو طرفه است، عدد رنگی یالی یا برابر است یا. وقتی گراف از کلاس ۱ و در غیر این صورت از کلاس ۲ خواند
ه می شود. تمام گراف های دوبخشی از کلاس ۱ هستند، و تقریباً تمام گراف های تصادفی نیز از کلاس ۱ هستند. اما به طور کلی مسئلهٔ تشخیص این که گرافی از کلاس ۱ هست یا نه، ان پی کامل است. ویزینگ (۱۹۶۵) ثابت کرد که گراف های مسطح با بیشینه درجهٔ حداقل هشت از کلاس ۱ هستند و حدس زد که برای گراف های مسطح با بیشینه درجهٔ هفت یا شش نیز درست باشد. از طرف دیگر گرافی های مسطحی با بیشینه درجهٔ دو تا پنج وجود دارند که از کلاس ۲ هستند. حدس گفته شده، پس از آن برای گراف های مسطح با بیشینه درجهٔ هفت اثبات شده است. گراف های مسطح مکعبی بدون پل همگی از کلاس ۱ هستند، که این مسئله معادلی از قضیهٔ چهاررنگ است. گراف های منتظم. ۱-عامل-بندی از یک گراف -منتظم، یک افراز از یال های گراف به تطابق های کامل است، که معادل -رنگ آمیزی-یالی گراف است. یعنی یک گراف ۱-عامل-بندی دارد اگر و فقط اگر از کلاس ۱ باشد. در یک حالت خاص، یک ۳-رنگ آمیزی-یالی از از یک گراف مکعبی (۳-منتظم) گاهی رنگ آمیزی تیت نامیده می شود. هر گراف منتظمی ۱-عامل-بندی ندارد، مانند گراف پترسن. در حالت کلی snarkها به گراف هایی گفته می شود که مانند گراف پترسن، ۳-منتظم و از کلاس ۲ هستند. بنا
به قضیهٔ کوئینگ (۱۹۱۶) هر گراف دو بخشی منتظم یک ۱-عامل-بندی دارد. این قضیه قبلاً به عنوان projective configurations مطرح شده بود و توسط ارنست استینیتز ثابت شد. گراف های چندگانه. برای گراف های چندگانه، که در آن ها ممکن است چند یال موازی دو رأس را چندبار به هم متصل کنند، نتیجه های مشابه به قضیهٔ ویزینگ ولی ضعیف تر از آن، عدد رنگی یالی گراف را به بیشینه درجه و چندگانگی گراف که بیشترین تعداد یال های موازی بین هر دو رأس از گراف را نشان می دهد، مربوط می کند. ساده ترین مثال برای نشان دادن این که قضیهٔ ویزینگ را نمی توان برای گراف های چندگانه تعمیم داد،گراف شانون است: گرافی چندگانه با سه رأس و سه دسته از یال های موازی، هر دسته به تعداد یال، که هر سه زوج از رأس ها را به هم متصل می کنند. در این مثال، (هر رأس به دو دسته از سه دسته یال های موازی متصل است) ولی عدد رنگی یالی گراف برابر است (در کل یال وجود دارد که هر دو تایی از آن ها مجاورند پس رنگ هر کدام از یال ها باید با بقیه متفاوت باشد). شانون(۱۹۴۹) در یک نتیجه که بعدها الهام بخش ویزینگ شد، نشان داد که بدترین حالت برای هر گراف چندگانه این است که . همچنین، برای هر گراف
چندگانه ، ، نامساوی ای که برای گراف های ساده (که ) به قضیهٔ ویزینگ منجر می شود. الگوریتم ها. از آن جا که مسئلهٔ امتحان کردن این که گرافی از کلاس ۱ هست یا نه، ان پی کامل است، هیچ الگوریتمی از زمان چندجمله ای وجود ندارد که گرافی را با تعداد رنگ های بهینه رنگ آمیزی یالی کند. با این وجود الگوریتم هایی طرح شده اند که یک یا چندی از این شرط ها را ندارند: بعضی فقط روی زیرمجموعه ای از گراف ها کار می کنند، بعضی همیشه از تعداد بهینهٔ رنگ استفاده نمی کنند، یا بعضی همیشه در زمان چندجمله ای اجرا نمی شوند. رنگ آمیزی بهینهٔ دسته هایی از گراف ها. در مورد گراف های دوبخشی یا برخی گرافهای مسطح با بیشینه درجهٔ ، تعداد رنگ های بهینه دقیقاً برابر است. کول، اُست و شیرا (۲۰۰۱) نشان دادند که رنگ آمیزی یالی بهینهٔ این گراف ها را با زمان تقریباً خطی می توان پیدا کرد که تعداد یال ها است. الگوریتم های ساده تر اما بعضاً کندتر توسط کول و هاپکرافت(۱۹۸۲) و آلن (۲۰۰۳) ارائه شدند. الگوریتم آلن (۲۰۰۳) با منتظم کردن گراف ورودی، بدون تغییر درجه و تغییر محسوس سایز گراف، شروع می کند: با ادغام کردم زوج هایی از رأس ها که عضو یک بخش هستند و سپس اضافه
کردن تعداد کمی رأس و یال دیگر. سپس اگر درجه فرد است، آلن یک تطابق کامل در زمان تقریباً خطی پیدا می کند، به آن یک رنگ نسبت می دهد و آن را از گراف حذف می کند، که در نتیجه درجه زوج می شود. در نهایت، آلن یک مشاهده از گابو (۱۹۷۶) اعمال می کند، که با انتخاب کردن متناوب زیرمجموعه هایی از یال ها در یک تور اویلری از گراف، آن را به دو زیرگراف منتظم تقسیم می کند، که در نتیجه مسئلهٔ رنگ آمیزی به دو زیرمسئله تقسیم می شود، و الگوریتم این دو زیرمسئله را به صورت بازگشتی حل می کند. زمان کل این الگوریتم از است. برای گراف های مسطح با بیشینه درجهٔ ، تعداد رنگ های بهینه دقیقاً است. با فرض می توان یک رنگ آمیزی یالی بهینه در زمان خطی پیدا کرد (کول و کوالیک ۲۰۰۸). الگوریتم هایی که از تعداد رنگ بیشتر از تعداد بهینه استفاده می کنند. میسرا و گریس (۱۹۹۲) و گابو و همکاران (۱۹۸۵) الگوریتم هایی با زمان چندجمله ای برای رنگ کردن هر گراف با رنگ ارائه می دهند که حد بالایی قضیهٔ ویزینگ است. برای گراف های چندگانه، کارلوف و شمویس(۱۹۸۷) الگوریتمی ارائه دادند که به اِلی آپفال نسبت دادند. در این الگوریتم ابتدا گراف چندگانهٔ با اضافه کردن یک رأس و مت
صل کردن آن به همهٔ رأس های فرد، گراف اویلری می شود، دور اویلری پیدا می شود، و یک جهت برای دور انتخاب می شود. سپس یک گراف دو بخشی که هر بخشش یک کپی از رأس های است درست می شود، و یک یال از رأس در بخش چپ به رأس در بخش راست رسم می شود اگر و فقط اگر دور اویلری جهت دار یک یال از به در داشته باشد. با یک رنگ آمیزی یالی برای گراف های دوبخشی رنگ می شود. هر دسته رنگ در متناظر یک دسته یال در می شود که بیشینه درجهٔ دو دارد؛ که یک اجتماعی از مسیرها و دورهای جدا از هم است. بنابراین به هر دسته رنگ در می توان سه دسته رنگ در نسبت داد. زمان این الگوریتم بستگی به زمان رنگ آمیزی یالی یک گراف دو بخشی دارد که با استفاده از الگوریتم کول، اُست و شیرا از است. تعداد رنگ هایی که این الگوریتم استفاده می کند حداکثر formula_1 است، که نزدیک ولی نه دقیقاً برابر حد شانون formula_2 است. این الگوریتم همچنین به طریقی سرراست می تواند به یک الگوریتم موازی تبدیل شود. در یک مقاله، کارلوف و شمویس همچنین یک الگوریتم خطی برای رنگ کردن گراف های چندگانه از بیشینه درجهٔ سه با چهار رنگ ارائه می کنند (که با هر دو حد ویزینگ و شانون مطابقت دارد) و بر پایه های
ساده استوار است: این الگوریتم یک رأس به گراف اضافه می کند تا گراف اویلری شود، یک دور اویلری پیدا می کند، و سپس متناوباً مجموعه هایی از یال ها را روی دور پیدا می کند به طوری که گراف به دو زیرگراف از بیشینه درجهٔ دو تقسیم شود. مسیرها و دورهای زوج هر زیرگراف را با دو رنگ می توان رنگ کرد. پس از این مرحله، هر کدام از دورهای فرد باقی مانده حداقل یک یال دارند که می توان آن را با یکی از دو رنگی که متعلق به زیرگراف دیگر است، رنگ کرد. این یال از دور فرد حذف می شود که در نتیجه یک مسیر باقی می ماند که با دو رنگ زیرگراف خود رنگ شده است. یک الگوریتم حریصانه که یال های گراف را یکی یکی بررسی می کند و به هر کدام اولین رنگ موجود را نسبت می دهد، گاهی تا عدد رنگ مصرف می کند که تقریباً دو برابر تعداد رنگ های مورد نیاز است. اما این برتری را دارد که می توان از این الگوریتم در زمینهٔ الگوریتم برخط استفاده کرد که در آن گراف ورودی از قبل مشخص نیست. در این زمینه، نسبت رقابتی این الگوریتم دو است که بهینه است: هیچ الگوریتم برخط دیگری نتوانسته است عملکرد بهتری داشته باشد. ولی اگر یال ها به ترتیبی رندم وارد شوند و گراف ورودی درجه ای حداقل
لگاریتمی داشته باشد، آن گاه می توان به نسبت های رقابتی بهتری دست یافت. تعدادی از مؤلفین حدس زده اند که بیان می کند که شاخص رنگی کسری هر گراف چندگانه (یک عدد که بتوان در زمان چندجمله ای با استفاده از برنامه نویسی خطی حساب کرد) یکی از شاخص های رنگی است. اگر این حدس ها درست باشد، این امکان وجود دارد که عددی را بتوان محاسبه کرد که برای مورد گراف های چندگانه هیچ گاه بیشتر از یک عدد از شاخص رنگی بیشتر نباشد، که در مورد گراف های ساده تطابق است: تا جایی که از طریق قضیهٔ ویزینگ می دانیم. با این که در حالت کلی اثبات نشده است، ولی این حدس ها تا جایی می دانیم برای حالتی که شاخص رنگی حداقل formula_3 باشد درست اند، حالتی که برای گراف های چندگانه با چندگانگی به اندازهٔ کافی بزرگ رخ می دهد. الگوریتم های دقیق. به راحتی می توان امتحان کرد که یک گراف را با یک رنگ یا دو رنگ می توان رنگ آمیزی یالی کرد یا نه. بنابراین اولین حالت غیربدیهی رنگ آمیزی یالی، امتحان کردن این است که گرافی ۳-رنگ آمیزی-یالی می شود یا نه. کوالیک(۲۰۰۹) نشان داد که می توان در زمان و با استفاده از حافظهٔ خطی، امتحان کرد یک گراف ۳-رنگ آمیزی-یالی دارد یا نه. با
این که این زمان نمایی است، ولی بسیار بهتر و سریع تر از امتحان کردن تمام حالت های ممکن نسبت دادن رنگ ها به یال هاست. هر گراف ۲-همبند ۳-منتظم با رأس، از عدد ۳-رنگ آمیزی-یالی دارد، که تمام آن ها را می توان در زمان به دست آورد (قدری کندتر از زمان لازم برای پیدا کردن یک رنگ آمیزی)؛ همانطور که گرگ کوپربرگ مشاهده کرد، گراف یک منشور بر یک -ضلعی رنگ آمیزی های بسیاری دارد، که نشان می دهد این حد و مرز محکم است. با اعمال کردن رنگ آمیزی رأسی به گراف خط گراف ورودی، می توان هر گرافی با یال را رنگ آمیزی یالی بهینه کرد، با زمان و حافظهٔ خطی یا زمان و حافظهٔ خطی (Björklund, Husfeldt &amp; Koivisto 2009). از آن جایی که رنگ آمیزی یالی حتی برای سه رنگ هم ان پی کامل است، بعید است که وقتی که بر حسب تعداد رنگ ها پارامتری شود، مهارشدنی با پارامتر ثابت باشد. با این وجود، برای پارامترهای دیگری مهارشدنی هست. در عمل، زو، ناکانو و نیشیزکی(۱۹۹۶) نشان دادند که برای گراف هایی با عرض درختی ، یک رنگ آمیزی بهینهٔ یالی در زمان قابل محاسبه است، زمانی که بر حسب فرانمایی است ولی برحسب تعداد رأس ها فقط خطی است. نمهاسر و پارک(۱۹۹۱) مسئلهٔ رنگ آمیزی
یالی را به عنوان یک برنامهٔ عدد صحیح فرمول بندی کردند و تجربهٔ خود را در استفاده از یک حل کنندهٔ برنامه نویسی عدد صحیح برای رنگ آمیزی یالی گراف ها توضیح دادند. ولی آن ها هیچ بررسی پیچیدگی زمان و حافظه ای برای الگوریتمشان ارائه ندادند. خصوصیات دیگر. یک گراف به صورت یکتا -رنگ پذیر-یالی است اگر بدون درنظرگرفتن جایگشت رنگ ها فقط یک راه برای تقسیم یال ها به کلاس رنگی وجود داشته باشد (بدون در نظر گرفتن جایگشت رنگ ها). برای تنها گراف های به صورت یکتا -رنگ پذیر-یالی، مسیر، دور و ستاره است. برای دیگر گراف ها نیز ممکن است به صورت یکتا -رنگ پذیر-یالی باشند. اگرچه همه گراف های ۳-رنگ پذیر همواره دارای دقیقاً سه دور همیلتونی هستند اما برعکس این موضوع صادق نیست یعنی گراف هایی با سه دور همیلتونی وجود دارند که به صورت یکتا ۳-رنگ پذیر-یالی نیستند همانند گراف های تعمیم یافتهٔ پترسن برای . تنها گراف غیر مسطح ۳-رنگ پذیر-یالی است و فرضیه ای وجود دارد که گرافی دیگر وجود ندارد. (Folkman &amp; Fulkerson 1969) دنباله غیر افزایشی ها از اعداد را بررسی کردند با این خصوصیت که یک رنگ آمیزی یالی مناسب از گراف وجود دارد که در آن گراف یال با
رنگ -ام وجود دارد. آن ها مشاهده کردند که اگر دنبالهٔ امکان پذیر باشد و در lexicographic order بزرگتر از دنبالهٔ با همان جمع باشد، دنباله نیز امکان پذیر است. اگر در lexicographic order داشته باشیم ، دنباله با تعدادی متناهی از مراحل می تواند به تبدیل شود. دراین مراحل از هریک از اعداد یکی کاسته می شود و به که یکی افزوده می شود. به بیان رنگ آمیزی یالی، از رنگی شروع می کنیم که توسط منتشر شده است. درهریک از مراحل رنگ های و در چرخه Kempe جابه جا می شوند. به طور مشخص هرگراف یک رنگ آمیزی یالی equitable دارد که در آن تعداد رنگ ها بهینه است و تعداد یال های هردورنگ متفاوت فقط یکی اختلاف داشته باشد. قضیه De Bruijn Erdos خصوصیات رنگ آمیزی گراف های متناهی به گراف های نامتناهی نیز منتقل می شود. برای مثال قضیه های شانون و ویزینگ که مربوط به درجه گراف و chromatic index هستند را می توان به گراف های نامتناهی تعمیم داد. (Richer 2011) مسئله پیدا کردن رسم گراف را برای گراف مکعبی با این خصوصیت که همه یال های رسم شده دارای یکی از سه slop متفاوت باشد و هیچ دویالی بر روی یک خط نباشند. اگر رسمی از وجود داشته باشد، slopها می تواند به عنو
ان رنگ ها در گراف ۳-رنگ پذیر استفاده شود. همانطور که Richer نشان می دهد گراف دو بخشی ۳-منتظم با رنگ آمیزی تایت داده شده را می توان اینگونه رنگ کرد اگروتنهااگر گراف ۳-همبند باشد. برای گراف غیرچندبخشی، شرایط کمی پیچیده تر است: یک رنگ آمیزی داده شده را می توان با رسم گراف نشان داد اگر bipartite double cover گراف ۳-همبند باشد و درصورتی که هریک از جفت یال های monochromatic را حذف کنیم بازهم حاصل گرافی غیردوبخشی باشد. این شرایط را ممکن است بتوان در زمان چندجمله ای بررسی کرد، اگرچه مسئله بررسی گراف ۴-رنگ شده ی-یالی ۴-منتظم با رسم ۴-slop دارای پیچیدگی زمانی NP-complete است. همان گونه که شاخص رنگی به بیشترین درجه و بیشترین تعداد تطابق های گراف مرتبط است، به linear arboricity گراف G نیز مرتبط است که آن را با نشان می دهد کمترین تعداد جنگل های خطی است که یال های گراف قابل افراز به آن جنگل ها باشند. یک تطابق حالت خاصی از جنگل خطی است و هر جنگل خطی، ۲-رنگ پذیر است. بنابراین برای هر گراف G داریم: . فرضیه Akiyama بیان می کند که formula_4 و این باید از رابطهٔ تبعیت کند. برای گراف با حداکثر درجه سه، همیشه مقدار دو می گیرد و بن
ابراین داریم که این همان حد قضیهٔ ویزینگ است. انواع دیگر رنگ آمیزی یالی. عدد تو، تعداد رنگ های لازم برای رنگ آمیزی یالی به این شرط است که در هر مسیر با طول زوج، دنبالهٔ رنگی نیمهٔ اول مسیر و نیمهٔ دوم آن متفاوت باشد. Arboricity یک گراف، کمترین تعداد رنگ لازم برای رنگ آمیزی است با این شرط که به جای اینکه هیچ دو یال مجاوری همرنگ نباشد، هیچ دو یالی که در یک دور قرار دارند همرنگ نباشند. این عدد بیانگر کمینه تعداد تقسیم بندی گراف به جنگل است. برخلاف شاخص رنگی، مقدار Arboricity را می توان در زمان چندجمله ای محاسبه کرد. رنگ آمیزی یالی لیستی، مسئله ایست که در آن گرافی داده شده است که در آن هر رأس، لیستی از رنگ ها را نگه می دارد و هدف پیدا کردن رنگ آمیزی یالی است بطوری که هر رأس با یکی از رنگ های لیست خودش رنگ شود. شاخص رنگی لیستی یک گراف، کوچکترین عددی مانند است بطوریکه اگر لیست رنگ ها حداقل رنگ داشته باشد، نحوه انتخاب رنگ از آن لیست فرقی نکند و درهرصورت رنگ آمیزی امکان پذیر باشد. بنابراین شاخص رنگی لیستی همواره از شاخص رنگی ناکوچکتر است.Dinitz conjecture در تکمیل مربع لاتین، شاخص رنگی لیستی در گراف های کامل دوبخشی ر
ا برابر با شاخص رنگی تعریف می کند. Galvin این فرضیه را به طور عمومی اثبات می کند: در هر گراف دو بخشی، مقادیر شاخص رنگی لیستی و شاخص رنگی با هم برابر است. این مسئله برای هر گراف دوبخشی دلخواه بدون دور کماکان بدون اثبات باقی مانده است. تعداد زیادی از مسائل رنگ آمیزی رئوس قابل گسترش به رنگ آمیزی یالی است. برای مثال رنگ آمیزی یالی کامل نوع یالی از رنگ آمیزی کامل (نوعی رنگ آمیزی گراف که در آن هر جفت رنگ به حداقل یک جفت راس مجاور نسبت داده می شود و هدف بیشینه کردن تعداد تمام رنگ هاست) است. رنگ آمیزی قوی یالی گراف نوع یالی از رنگ آمیزی قوی است که در آن به هر دو یالی که به یک رأس ختم می شوند باید رنگ های متفاوتی نسبت داده شود. رنگ آمیزی قوی یالی در زمینه هایی همچون تخصیص شمای کانال در شبکه های بی سیم کاربرد دارد. رنگ آمیزی بدون دور یالی یکی از انواع رنگ آمیزی بدون دور است که در آن هردو کلاس رنگی، یک زیرگراف بدون دور را تشکیل می دهد (که یک جنگل است). (Eppstein 2008) دربارهٔ رنگ آمیزی یالی سه گانه برای گراف های مکعبی با خصوصیات اضافی مطالعه کرد. در این رنگ آمیزی هیچ دو دور bichromaticی که بیش از یک یال مشترک دارند، وجو
د ندارد. وی نشان داد که وجود رنگ برای این مسئله معادل رسم گراف در محیط سه بعدی شطرنجی است که در آن یال های موازی معادل محورهای هم پایه و پایه های موازی شامل حداکثر دو یال می شود. البته ذکر این نکته ضروری است که حل این مسئله نیز مانند حل مسئله استاندارد رنگ آمیزی سه گانه NP-complete است. رنگ آمیزی تام، شکلی از رنگ آمیزی است که از ترکیب رنگ آمیزی یالی و رأسی به وجود آمده است و باید همه راس ها و یال ها رنگ شوند. هر زوج رأس و یال مجاور یا دویال مجاور و همچنین هر دو رأس مجاور باید رنگ های متفاوتی داشته باشند. فرضیه ای اثبات نشده از ترکیب قضیهٔ ویزینگ و brooks به وجود می آید که می گوید برای هر گراف، تعداد رنگ های لازم برای رنگ آمیزی تام برابر بیشترین درجه گراف به اضافه دو است. اگر گراف ۳-منتظم روی یک سطح با سه رنگ قابل رنگ آمیزی باشد، گراف مکمل آن که سطح را به مثلث های هم مساحت افراز می کند نیز قابل رنگ آمیزی یالی است (هرچند در حالت کلی، ممکن است رنگ آمیزی نادرست یالی باشد). رنگ آمیزی بدین صورت انجام می گیرد که هر مثلث یک یال از هر رنگ را دارد. دیگر رنگ آمیزی ها و چرخش های مثلث ها با محدودیت ها خاص بر روی چگونگی مر
تب شدن رنگ های رئوس، می تواند برای کد کردن انواع مختلف اشکال هندسی به کار برده شود. برای مثال تقسیم مستطیلی (تقسیم به مستطیل های کوچکتر بطوری که هر سه مستطیل کنار هم در یک رأس مشترک باشند) را می توان درقالب برچسب گذاری منظم به صورت رنگ آمیزی دوتایی یال های مستطیل مکمل تعریف کرد با این محدودیت که هر یال در برخورد با هر رأس، چهار زیرمجموعهٔ پیوسته را ایجاد می کند که در آن ها رنگ آمیزی ها یکسان است. این برچسب گذاری، مکمل رنگ آمیزی مستطیلی است که در آن هر یال عمودی یک رنگ و هریال افقی نیز رنگ دیگری دارد. برای هریک از این سه نوع برچست گذاری منظم، مجموعه ای از گراف های برچسب گذاری شده یک شبکه توزیع شده را تشکیل می دهند که برای لیست کردن سریع ساختارهای هندسی براساس همان گراف یا پیدا کردن محدودیت های بیشتر به کار می رود. یک deterministic finite automaton به عنوان یک گراف مستقیم تفسیر می شود که در آن هر رأس درجهٔ خروجی d را دارد و یال ها d-رنگ پذیرند بطوری که یال ها با رأس مبدأ مشترک، رنگ ها متفاوتی دارند. مسئلهٔ رنگ آمیزی جاده ها، مسئلهٔ رنگ آمیزی یالی گراف مستقیم است که automatonهای را نتیجه می دهد که synchronizing
word دارند. (Trahtman 2009) این مسئله را با اثبات این مطلب که اگر گراف قویاً همبند و نامتناوب باشد چنین رنگ آمیزی وجود دارد، حل کرده است. تئوری Ramsey به مسئلهٔ رنگ آمیزی -تایی گراف کامل مربوط می شود که از ساختن زیرگراف کامل از سایز داده شدهٔ که monochromatic باشد جلوگیری می کند. بر اساس این تئوری عددی مانند وجود دارد که هرگاه رنگ آمیزی امکان پذیر نخواهد بود. برای مثال در گراف با اگر یال ها ۲-رنگ شده باشد، حتماً مستطیل monochromatic وجود دارد. کاربردها. برای زمان بندی مسابقات گردشی می توان رنگ آمیزی یالی یک گراف کامل را به کار برد. بدین صورت می توان در کمترین تعداد گردش این مسابقات را زمان بندی کرد بطوری که همه تیم ها در هر گردش بازی کنند. در این مسئله تیم ها به صورت رئوس و بازی ها به صورت یال مدل می شوند. بنابراین تعداد گردش ها برابراست با تعداد رنگ های مورد استفاده برای رنگ آمیزی یالی. برای زمان بندی مسابقاتی که همهٔ تیم ها با یکدیگر بازی نمی کند نیز می توان از تکنیک های دیگر رنگ آمیزی یالی استفاده کرد. برای مثال در لیگ جهانی فوتبال، جفت تیم هایی که باید در طول یک سال با هم بازی کنند، براساس نتایج سالیان قب