payamvha/North_RAG huggingface dataset:
ولی ۳-رنگ‌آمیزی-یالی ندارد. رابطه با درجه. قضیهٔ ویزینگ. عدد رنگی یالی یک گراف رابطهٔ نزدیکی با بیشینه درجهٔ آن گراف ، بیشترین تعداد ممکن یال مجاور به هر رأسی از آن گراف، دارد. واضحاً زیرا اگر یال متفاوت همگی به یک رأس برسند، آن‌گاه همهٔ آن‌ها باید رنگی متفاوت از دیگری داشته باشند و این امر هنگامی ممکن است که حداقل رنگ متمایز برای نسبت دادن به آن‌ها وجود داشته باشد. قضیهٔ ویزینگ (نامیده شده به خاطر ودیم جی ویزینگ که این قضیه را در ۱۹۶۴ اثبات و منتشر کرد) بیان می‌کند که این مرز تقریباً دو طرفه است، عدد رنگی
می‌کند که این مرز تقریباً دو طرفه است، عدد رنگی یالی یا برابر است یا. وقتی گراف از کلاس ۱ و در غیر این صورت از کلاس ۲ خوانده می‌شود. تمام گراف‌های دوبخشی از کلاس ۱ هستند، و تقریباً تمام گراف‌های تصادفی نیز از کلاس ۱ هستند. اما به‌طور کلی مسئلهٔ تشخیص این که گرافی از کلاس ۱ هست یا نه، ان‌پی کامل است. ویزینگ (۱۹۶۵) ثابت کرد که گراف‌های مسطح با بیشینه درجهٔ حداقل هشت از کلاس ۱ هستند و حدس زد که برای گراف‌های مسطح با بیشینه درجهٔ هفت یا شش نیز درست باشد. از طرف دیگر گرافی‌های مسطحی با بیشینه درجهٔ دو تا پنج
دیگر گرافی‌های مسطحی با بیشینه درجهٔ دو تا پنج وجود دارند که از کلاس ۲ هستند. حدس گفته شده، پس از آن برای گراف‌های مسطح با بیشینه درجهٔ هفت اثبات شده‌است. گراف‌های مسطح مکعبی بدون پل همگی از کلاس ۱ هستند، که این مسئله معادلی از قضیهٔ چهاررنگ است. گراف‌های منتظم. ۱-عامل-بندی از یک گراف -منتظم، یک افراز از یال‌های گراف به تطابق‌های کامل است، که معادل -رنگ‌آمیزی-یالی گراف است. یعنی یک گراف ۱-عامل-بندی دارد اگر و فقط اگر از کلاس ۱ باشد. در یک حالت خاص، یک ۳-رنگ‌آمیزی-یالی از از یک گراف مکعبی (۳-منتظم) گاهی رنگ
از از یک گراف مکعبی (۳-منتظم) گاهی رنگ آمیزی تیت نامیده می‌شود. هر گراف منتظمی ۱-عامل-بندی ندارد، مانند گراف پترسن. در حالت کلی snarkها به گراف‌هایی گفته می‌شود که مانند گراف پترسن، ۳-منتظم و از کلاس ۲ هستند. بنا به قضیهٔ کوئینگ (۱۹۱۶) هر گراف دو بخشی منتظم یک ۱-عامل-بندی دارد. این قضیه قبلاً به عنوان projective configurations مطرح شده بود و توسط ارنست استینیتز ثابت شد. گراف‌های چندگانه. برای گراف‌های چندگانه، که در آن‌ها ممکن است چند یال موازی دو رأس را چندبار به هم متصل کنند، نتیجه‌های مشابه به قضیهٔ
چندبار به هم متصل کنند، نتیجه‌های مشابه به قضیهٔ ویزینگ ولی ضعیف‌تر از آن، عدد رنگی یالی گراف را به بیشینه درجه و چندگانگی گراف که بیشترین تعداد یال‌های موازی بین هر دو رأس از گراف را نشان می‌دهد، مربوط می‌کند. ساده‌ترین مثال برای نشان دادن این که قضیهٔ ویزینگ را نمی‌توان برای گراف‌های چندگانه تعمیم داد،گراف شانون است: گرافی چندگانه با سه رأس و سه دسته از یال‌های موازی، هر دسته به تعداد یال، که هر سه زوج از رأس‌ها را به هم متصل می‌کنند. در این مثال، (هر رأس به دو دسته از سه دسته یال‌های موازی متصل است) ولی
به دو دسته از سه دسته یال‌های موازی متصل است) ولی عدد رنگی یالی گراف برابر است (در کل یال وجود دارد که هر دو تایی از آن‌ها مجاورند پس رنگ هر کدام از یال‌ها باید با بقیه متفاوت باشد). شانون(۱۹۴۹) در یک نتیجه که بعدها الهام‌بخش ویزینگ شد، نشان داد که بدترین حالت برای هر گراف چندگانه این است که . همچنین، برای هر گراف چندگانه ، ، نامساوی‌ای که برای گراف‌های ساده (که ) به قضیهٔ ویزینگ منجر می‌شود. الگوریتم‌ها. از آن جا که مسئلهٔ امتحان کردن این که گرافی از کلاس ۱ هست یا نه، ان‌پی کامل است، هیچ الگوریتمی از زمان
هست یا نه، ان‌پی کامل است، هیچ الگوریتمی از زمان چندجمله‌ای وجود ندارد که گرافی را با تعداد رنگ‌های بهینه رنگ‌آمیزی یالی کند. با این وجود الگوریتم‌هایی طرح شده‌اند که یک یا چندی از این شرط‌ها را ندارند: بعضی فقط روی زیرمجموعه‌ای از گراف‌ها کار می‌کنند، بعضی همیشه از تعداد بهینهٔ رنگ استفاده نمی‌کنند، یا بعضی همیشه در زمان چندجمله‌ای اجرا نمی‌شوند. رنگ‌آمیزی بهینهٔ دسته‌هایی از گراف‌ها. در مورد گراف‌های دوبخشی یا برخی گرافهای مسطح با بیشینه درجهٔ ، تعداد رنگ‌های بهینه دقیقاً برابر است. کول، اُست و شیرا
رنگ‌های بهینه دقیقاً برابر است. کول، اُست و شیرا (۲۰۰۱) نشان دادند که رنگ‌آمیزی یالی بهینهٔ این گراف‌ها را با زمان تقریباً خطی می‌توان پیدا کرد که تعداد یال‌ها است. الگوریتم‌های ساده‌تر اما بعضاً کندتر توسط کول و هاپکرافت(۱۹۸۲) و آلن (۲۰۰۳) ارائه شدند. الگوریتم آلن (۲۰۰۳) با منتظم کردن گراف ورودی، بدون تغییر درجه و تغییر محسوس سایز گراف، شروع می‌کند: با ادغام کردم زوج‌هایی از رأس‌ها که عضو یک بخش هستند و سپس اضافه کردن تعداد کمی رأس و یال دیگر. سپس اگر درجه فرد است، آلن یک تطابق کامل در زمان تقریباً خطی
فرد است، آلن یک تطابق کامل در زمان تقریباً خطی پیدا می‌کند، به آن یک رنگ نسبت می‌دهد و آن را از گراف حذف می‌کند، که در نتیجه درجه زوج می‌شود. در نهایت، آلن یک مشاهده از گابو (۱۹۷۶) اعمال می‌کند، که با انتخاب کردن متناوب زیرمجموعه‌هایی از یال‌ها در یک تور اویلری از گراف، آن را به دو زیرگراف منتظم تقسیم می‌کند، که در نتیجه مسئلهٔ رنگ‌آمیزی به دو زیرمسئله تقسیم می‌شود، و الگوریتم این دو زیرمسئله را به صورت بازگشتی حل می‌کند. زمان کل این الگوریتم از است. برای گراف‌های مسطح با بیشینه درجهٔ ، تعداد رنگ‌های بهینه
مسطح با بیشینه درجهٔ ، تعداد رنگ‌های بهینه دقیقاً است. با فرض می‌توان یک رنگ‌آمیزی یالی بهینه در زمان خطی پیدا کرد (کول و کوالیک ۲۰۰۸). الگوریتم‌هایی که از تعداد رنگ بیشتر از تعداد بهینه استفاده می‌کنند. میسرا و گریس (۱۹۹۲) و گابو و همکاران (۱۹۸۵) الگوریتم‌هایی با زمان چندجمله‌ای برای رنگ کردن هر گراف با رنگ ارائه می‌دهند که حد بالایی قضیهٔ ویزینگ است. برای گراف‌های چندگانه، کارلوف و شمویس(۱۹۸۷) الگوریتمی ارائه دادند که به اِلی آپفال نسبت دادند. در این الگوریتم ابتدا گراف چندگانهٔ با اضافه کردن یک رأس و
ابتدا گراف چندگانهٔ با اضافه کردن یک رأس و متصل کردن آن به همهٔ رأس‌های فرد، گراف اویلری می‌شود، دور اویلری پیدا می‌شود، و یک جهت برای دور انتخاب می‌شود. سپس یک گراف دو بخشی که هر بخشش یک کپی از رأس‌های است درست می‌شود، و یک یال از رأس در بخش چپ به رأس در بخش راست رسم می‌شود اگر و فقط اگر دور اویلری جهت دار یک یال از به در داشته باشد. با یک رنگ‌آمیزی یالی برای گراف‌های دوبخشی رنگ می‌شود. هر دسته رنگ در متناظر یک دسته یال در می‌شود که بیشینه درجهٔ دو دارد؛ که یک اجتماعی از مسیرها و دورهای جدا از هم است.
که یک اجتماعی از مسیرها و دورهای جدا از هم است. بنابراین به هر دسته رنگ در می‌توان سه دسته رنگ در نسبت داد. زمان این الگوریتم بستگی به زمان رنگ‌آمیزی یالی یک گراف دو بخشی دارد که با استفاده از الگوریتم کول، اُست و شیرا از است. تعداد رنگ‌هایی که این الگوریتم استفاده می‌کند حداکثر formula_1 است، که نزدیک ولی نه دقیقاً برابر حد شانون formula_2 است. این الگوریتم همچنین به طریقی سرراست می‌تواند به یک الگوریتم موازی تبدیل شود. در یک مقاله، کارلوف و شمویس همچنین یک الگوریتم خطی برای رنگ کردن گراف‌های چندگانه از
یک الگوریتم خطی برای رنگ کردن گراف‌های چندگانه از بیشینه درجهٔ سه با چهار رنگ ارائه می‌کنند (که با هر دو حد ویزینگ و شانون مطابقت دارد) و بر پایه‌های ساده استوار است: این الگوریتم یک رأس به گراف اضافه می‌کند تا گراف اویلری شود، یک دور اویلری پیدا می‌کند، و سپس متناوباً مجموعه‌هایی از یال‌ها را روی دور پیدا می‌کند به طوری که گراف به دو زیرگراف از بیشینه درجهٔ دو تقسیم شود. مسیرها و دورهای زوج هر زیرگراف را با دو رنگ می‌توان رنگ کرد. پس از این مرحله، هر کدام از دورهای فرد باقی‌مانده حداقل یک یال دارند که
از دورهای فرد باقی‌مانده حداقل یک یال دارند که می‌توان آن را با یکی از دو رنگی که متعلق به زیرگراف دیگر است، رنگ کرد. این یال از دور فرد حذف می‌شود که در نتیجه یک مسیر باقی می‌ماند که با دو رنگ زیرگراف خود رنگ شده‌است. یک الگوریتم حریصانه که یال‌های گراف را یکی یکی بررسی می‌کند و به هر کدام اولین رنگ موجود را نسبت می‌دهد، گاهی تا عدد رنگ مصرف می‌کند که تقریباً دو برابر تعداد رنگ‌های مورد نیاز است. اما این برتری را دارد که می‌توان از این الگوریتم در زمینهٔ الگوریتم برخط استفاده کرد که در آن گراف ورودی از
الگوریتم برخط استفاده کرد که در آن گراف ورودی از قبل مشخص نیست. در این زمینه، نسبت رقابتی این الگوریتم دو است که بهینه است: هیچ الگوریتم برخط دیگری نتوانسته است عملکرد بهتری داشته باشد. ولی اگر یال‌ها به ترتیبی رندم وارد شوند و گراف ورودی درجه‌ای حداقل لگاریتمی داشته باشد، آن‌گاه می‌توان به نسبت‌های رقابتی بهتری دست یافت. تعدادی از مؤلفین حدس زده‌اند که بیان می‌کند که شاخص رنگی کسری هر گراف چندگانه (یک عدد که بتوان در زمان چندجمله‌ای با استفاده از برنامه‌نویسی خطی حساب کرد) یکی از شاخص‌های رنگی است. اگر
خطی حساب کرد) یکی از شاخص‌های رنگی است. اگر این حدس‌ها درست باشد، این امکان وجود دارد که عددی را بتوان محاسبه کرد که برای مورد گراف‌های چندگانه هیچ‌گاه بیشتر از یک عدد از شاخص رنگی بیشتر نباشد، که در مورد گراف‌های ساده تطابق است: تا جایی که از طریق قضیهٔ ویزینگ می‌دانیم. با این که در حالت کلی اثبات نشده‌است، ولی این حدس‌ها تا جایی می‌دانیم برای حالتی که شاخص رنگی حداقل formula_3 باشد درست‌اند، حالتی که برای گراف‌های چندگانه با چندگانگی به اندازهٔ کافی بزرگ رخ می‌دهد. الگوریتم‌های دقیق. به راحتی می‌توان
رخ می‌دهد. الگوریتم‌های دقیق. به راحتی می‌توان امتحان کرد که یک گراف را با یک رنگ یا دو رنگ می‌توان رنگ‌آمیزی یالی کرد یا نه. بنابراین اولین حالت غیربدیهی رنگ‌آمیزی یالی، امتحان کردن این است که گرافی ۳-رنگ‌آمیزی-یالی می‌شود یا نه. کوالیک(۲۰۰۹) نشان داد که می‌توان در زمان و با استفاده از حافظهٔ خطی، امتحان کرد یک گراف ۳-رنگ‌آمیزی-یالی دارد یا نه. با این که این زمان نمایی است، ولی بسیار بهتر و سریع‌تر از امتحان کردن تمام حالت‌های ممکن نسبت دادن رنگ‌ها به یال‌هاست. هر گراف ۲-همبند ۳-منتظم با رأس، از عدد
یال‌هاست. هر گراف ۲-همبند ۳-منتظم با رأس، از عدد ۳-رنگ‌آمیزی-یالی دارد، که تمام آن‌ها را می‌توان در زمان به دست‌آورد (قدری کندتر از زمان لازم برای پیدا کردن یک رنگ‌آمیزی)؛ همانطور که گرگ کوپربرگ مشاهده کرد، گراف یک منشور بر یک -ضلعی رنگ‌آمیزی‌های بسیاری دارد، که نشان می‌دهد این حد و مرز محکم است. با اعمال کردن رنگ‌آمیزی رأسی به گراف خط گراف ورودی، می‌توان هر گرافی با یال را رنگ‌آمیزی یالی بهینه کرد، با زمان و حافظهٔ خطی یا زمان و حافظهٔ خطی (Björklund, Husfeldt &amp; Koivisto 2009). از آن‌جایی که رنگ‌آمیزی
&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 گراف ۳-همبند
نشان داد اگر 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 را دارد و یال‌ها d-رنگ‌پذیرند بطوری که یال‌ها با رأس مبدأ مشترک، رنگ‌ها متفاوتی دارند. مسئلهٔ رنگ‌آمیزی جاده‌ها، مسئلهٔ رنگ‌آمیزی یالی گراف مستقیم است که automatonهای را نتیجه می‌دهد که synchronizing word دارند. (Trahtman 2009) این مسئله را با اثبات این مطلب که اگر گراف قویاً همبند و نامتناوب باشد چنین رنگ‌آمیزی وجود دارد، حل کرده‌است. تئوری Ramsey به مسئلهٔ رنگ‌آمیزی -تایی گراف کامل مربوط می‌شود که از ساختن زیرگراف کامل از سایز داده شدهٔ که monochromatic باشد جلوگیری می‌کند.
داده شدهٔ که monochromatic باشد جلوگیری می‌کند. بر اساس این تئوری عددی مانند وجود دارد که هرگاه رنگ‌آمیزی امکان‌پذیر نخواهد بود. برای مثال در گراف با اگر یال‌ها ۲-رنگ‌شده باشد، حتماً مستطیل monochromatic وجود دارد. کاربردها. برای زمان‌بندی مسابقات گردشی می‌توان رنگ‌آمیزی یالی یک گراف کامل را به کار برد. بدین صورت می‌توان در کمترین تعداد گردش این مسابقات را زمان‌بندی کرد بطوری که همه تیم‌ها در هر گردش بازی کنند. در این مسئله تیم‌ها به صورت رئوس و بازی‌ها به صورت یال مدل می‌شوند. بنابراین تعداد گردش‌ها
به صورت یال مدل می‌شوند. بنابراین تعداد گردش‌ها برابراست با تعداد رنگ‌های مورد استفاده برای رنگ‌آمیزی یالی. برای زمان‌بندی مسابقاتی که همهٔ تیم‌ها با یکدیگر بازی نمی‌کند نیز می‌توان از تکنیک‌های دیگر رنگ‌آمیزی یالی استفاده کرد. برای مثال در لیگ جهانی فوتبال، جفت تیم‌هایی که باید در طول یک سال با هم بازی کنند، براساس نتایج سالیان قبلی تعیین می‌شود. زمان‌بندی بازی‌ها از اجرای الگوریتم رنگ‌آمیزی یالی بر روی گرافی به دست می‌آید که از جفت تیم‌ها ساخته شده‌است.. برای این کاربرد، قضیهٔ ویزینگ بیان می‌کند که مستقل
این کاربرد، قضیهٔ ویزینگ بیان می‌کند که مستقل از این که جفت تیم‌ها چگونه انتخاب شده باشند (به شرط این که هیچ دو تیمی در یک فصل دو بار با هم بازی نکنند)، همواره می‌توان زمان‌بندی‌ای استفاده کرد که حداکثر یک هفته بیشتر از تعداد تیم‌ها طول بکشد. زمان‌بندی Open Shop یک مسئلهٔ زمان‌بندی فرایندهای تولید است. در این مسئله، مجموعه‌ای از محصولات باید تولید شوند و هر محصول برای تولید نیازمند اجرای مجموعه‌ای از وظایف است. هر وظیفه باید روی ماشین‌های خاصی اجرا شود و زمان‌بندی باید به صورتی انجام شود که وظایف به یک
زمان‌بندی باید به صورتی انجام شود که وظایف به یک ماشین به‌طور همزمان نیاز نداشته باشند. اگر همه وظایف طول یکسانی داشته باشند، در این صورت مسئله به رنگ‌آمیزی گراف دوبخشی‌ای مدل می‌شود که رئوس در یک بخش گراف نشان‌دهندهٔ محصولات و رئوس بخش دیگر نشان‌دهنده ماشین‌ها هستند و یال‌ها نشان‌دهندهٔ وظایف هستند. بنابراین تعداد رنگ‌ها نشان‌دهندهٔ تعداد گام‌های زمانی برای اجرای وظایف هستند. از آن جایی که رنگ‌آمیزی گراف‌های دو بخشی در زمان چندجمله‌ای قابل انجام است، این مسئله نیز در زمان چندجمله‌ای قابل حل است. (Gandham,
نیز در زمان چندجمله‌ای قابل حل است. (Gandham, Dawande &amp; Prakash 2005) مسئله زمان‌بندی لینک‌ها برای پروتکل time division multiple access شبکه‌های کامپوتری بر روی شبکه‌های حسگر مطالعه کردند و راه‌حلی با رنگ‌آمیزی یالی ارائه دادند. در این مسئله باید بازه‌های زمانی برای یال‌های شبکه ارتباطی بی‌سیم انتخاب شود تا هر گره شبکه بتواند با گره‌های همسایه‌اش بدون تداخل ارتباط برقرار کند. استفاده از رنگ‌آمیزی یالی قوی (استفاده از دو بازه زمانی برای هر رنگ یال هریک برای یک جهت) مسئله را حل می‌کند ولی ممکن است تعداد
یک جهت) مسئله را حل می‌کند ولی ممکن است تعداد بیشتری بازه زمانی مورد نیاز باشد. به جای اینکار به دنبال رنگ‌آمیزی گراف مستقیم گشتند. گراف مستقیم از دوبله کردن یال‌های غیرمستقیم شبکه تشکیل می‌شود. این گراف این خصوصیت را دارد که رنگ هر یال مستقیم با رنگ یال‌های دیگر و همچنین رنگ یال‌های همسایه‌های متفاوت باشد. آن‌ها برای این مسئله یک الگوریتم اکتشافی براساس الگوریتم توزیع شده برای -رنگ‌آمیزی-یالی پیشنهاد دادند. در این الگوریتم پس پردازشی برای زمان‌بندی دوباره یال‌های متداخل تعبیه شده‌است. در ارتباطات فیبر
یال‌های متداخل تعبیه شده‌است. در ارتباطات فیبر نوری، رنگ‌آمیزی مسیر مسئله‌ایست که رنگ‌ها به جفت رئوسی که با هم ارتباط دارند، اختصاص می‌یابد. مسیرها در فیبرنوری ارتباطات شبکه را برای هر رأس را نشان می‌دهد. محدودیت این است که هیچ دو مسیری که قسمت مشترکی از فیبر را تسهیم می‌کنند از فرکانس یکسانی استفاده نکنند. مسیرها می‌توانند از سوئیچ ارتباطی یکسانی عبور کنند ولی از قسمت مشترکی از فیبر با فرکانس یکسان نمی‌توانند عبور کنند. وقتی توپولوژی شبکه به صورت ستاره‌ای باشد بدین صورت که سوئیچ در مرکز قرار دارد و هر گره
بدین صورت که سوئیچ در مرکز قرار دارد و هر گره با فیبرنوری جداگانه‌ای به سوئیچ متصل شده‌است، مسئلهٔ رنگ‌آمیزی مسیر تبدیل به رنگ‌آمیزی یالی گراف یا گراف چندگانه می‌شود. در این حالت گره‌ها همان رئوس گراف هستند و جفت گره‌هایی که با هم ارتباط برقرار می‌کنند، یال‌ها خواهند بود. تعداد رنگ‌های به کار رفته در رنگ‌آمیزی یالی، تعداد فرکانس‌های مورد استفاده در ارتباطات بین جفت گره‌هاست. برای ارتباطات شبکه‌ای با توپولوژی درختی، راه‌حل رنگ‌آمیزی مسیر برای شبکه‌های محلی حول هر سوئیچ به‌کاربرده می‌شود و از تجمیع این
حول هر سوئیچ به‌کاربرده می‌شود و از تجمیع این راه‌حل‌ها با یکدیگر مسئله نهایی حل خواهد شد. مسائل باز. جنسن و تافت(۱۹۹۵) لیستی از ۲۳ مسئلهٔ بار در رابطه با رنگ‌آمیزی یالی ارائه دادند. این لیست عبارت است از: یک حدس اخیر این است که اگر گراف چندگانهٔ -منتظم مسطح باشد، آن‌گاه ، -رنگ‌پذیر است اگر و فقط اگر ، -همبند یالی باشد. این قضیه می‌تواند به عنوان تعمیمی از قضیهٔ چهاررنگ باشد که =۳. ماریا چادنوسکی، کاترین ادواردز و پاول سیمور ثابت کردند که یک گراف چندگانهٔ ۸-منتظم یک عدد رنگی یالی ۸ دارد.
والنتین نیکولاویچ ولوشینوف (زادهٔ ۱۸ ژوئن ۱۸۹۵ در سن پترزبورگ – درگذشتهٔ ۱۳ ژوئن ۱۹۳۶ در لنین گراد) زبان‌شناس اهل اتحاد جماهیر شوروی سابق بود که آثارش در حوزه نظریه ادبی و نظریه مارکسیستی ایدئولوژی بسیار تأثیرگذار بوده‌است. او در دهه بیست قرن بیستم میلادی کتابی به نام «مارکسیسم و فلسفه زبان» منتشر ساخت. او در این کتاب یافته‌های زبان‌شناسی را وارد مباحث مارکسیسم کرد.
آرتور روبینشتاین (۲۸ ژانویهٔ ۱۸۸۷ – ۲۰ دسامبر ۱۹۸۲) نوازنده پیانو لهستانی–آمریکایی بود. او نه تنها در زمان حیاتش یکی از نوابغ نوازندگی پیانو بود بلکه هم‌اکنون نیز او را به‌عنوان یکی از بزرگترین نوازندگان مطرح آثار شوپن می‌شناسند. روبنشتاین بیش از ۲۰۰ اثر ضبط نمود. وی در ۱۹۷۶ میلادی نشان آزادی آمریکا را دریافت کرد. به عقیده بسیاری او یکی از برترین نوازندگان پیانو در تاریخ به‌شمار می‌رود زندگی. سال‌های آغازین. روبینشتاین از سه سالگی به آموختن موسیقی پرداخت. هفت ساله بود که برای نخستین بار در انظار عموم به
هفت ساله بود که برای نخستین بار در انظار عموم به اجرا پرداخت. در نه سالگی به برلین رفت و زیر نظر کارل هینریش بارث آموزش دید. در سال ۱۹۰۰ زمانی که ۱۳ سال داشت برای نخستین بار با فیلارمونیک برلین به اجرای زنده پرداخت. در ۱۹۰۶ نخستین اجرای زنده‌اش در آمریکا را همراه با ارکستر فیلادلفیا در تالار کارنگی به نمایش گذارد اما به دلیل جوانیش بازخورد سردی دریافت کرد. روبنشتاین که به هشت زبان مسلط بود، در طول جنگ جهانی اول در لندن به عنوان مترجم نظامی مشغول به کار شد. او در آنجا همراه با نوازنده ویلن، اوژن ایزایی به
او در آنجا همراه با نوازنده ویلن، اوژن ایزایی به اجرا پرداخت. سال‌های میانی. روبینشتاین از ۱۹۱۶ تا ۱۹۱۸ به اسپانیا و آمریکای جنوبی سفر کرد و با معرفی آثار مانوئل د فایا، ایساک آلبنیس و انریکه گرانادس احساسات حضار را برانگیخت. در ۱۹۱۹ بار دیگر به آمریکا سفر کرد. او در دهه ۱۹۲۰ میلادی شهرت و اعتباری جهانی کسب نمود. در ۱۹۳۲ ازدواج کرد و تصمیم گرفت که هنرش را مورد کاوش قرار دهد. او روزی ۱۲ تا ۱۶ ساعت به تمرین پرداخت و تکنیک یکتایش را نظم بخشید. در ۱۹۳۶ بار دیگر به ایالات متحده آمریکا بازگشت و در تالار کارنگی