stanford-oval/wikipedia huggingface dataset:
رنگ‌آمیزی یالی
تعریف

رنگ‌آمیزی یالی به انتساب رنگی مناسب به هر یال گفته می‌شود به صورتی که به هیچ دو یال مجاور، رنگ یکسانی منتسب نشود. در این تعریف دو یال مجاور به دو یالی گفته می‌شود که رأس مشترک داشته باشند. رنگ‌آمیزی یالیی گراف G معادل رنگ‌آمیزی رئوس گراف خطی L(G) است. گراف خطی L(G) گرافی است که به ازای هر یال G یک رأس دارد و یال‌های آن معادل جفت یال‌های مجاور در G است.
به رنگ‌آمیزی یالی با k رنگ مختلف k-رنگ‌آمیزی-یالی گفته می‌شود. به گرافی که این‌گونه قابل رنگ‌آمیزی باشد k-رنگ‌پذیر-یالی گفته می‌شود. کمترین تعداد رنگ برای رنگ‌آمیزی یالی یک گراف را شاخص رنگی یا عدد رنگی یال گراف می‌گویند و آن را با χ′(G) نشان می‌دهند. همچنین شاخص رنگی را گاهی با نماد χ۱(G) نشان می‌دهند که اندیس ۱ نشان‌دهنده یک بُعدی بودن یال‌هاست. گرافی که که شاخص رنگی آن k باشد را k-شاخص-یالی می‌نامند. نکتهٔ قابل توجه در اینجا این است که شاخص رنگی با عدد رنگی متفاوت است. عدد رنگی کمترین تعداد رنگ‌ها برای رنگ‌آمیزی رئوس گراف است و با χ(G) یا χ۰(G) نشان داده می‌شود.
در صورتی که ذکر نشود همه گراف‌ها را گراف ساده فرض می‌کنیم. در مقابل گراف ساده، گراف‌های چندگانه تعریف می‌شود که گرافی است که یال‌ها بتوانند ابتدا و انتهای یکسانی داشته باشند یعنی بین دو رأس چندین یال وجود داشته باشد یا گراف طوقه داشته باشد. در بسیاری از مسائل رنگ‌آمیزی یالی، الگوریتم‌ها برای گراف ساده و گراف چندگانه متفاوت خواهد بود و برای تبدیل راه‌حل‌های رنگ‌آمیزی گراف ساده به گراف چندگانه ملاحظات بسیاری مورد نیاز است.
رابطه با تطابق

یک تطابق در گراف G مجموعه‌ای از یال‌های نامجاور است؛ یک تطابق کامل یک تطابق است که یال‌های آن تمامی رأس‌ها را پوشش داده باشند، و تطابق بیشینه تطابقی است که بیشینه یال‌های ممکن را داراست. در رنگ‌آمیزی یالی، مجموعه یال‌های دارای یک رنگ خاص باید نامجاور باشند پس تشکیل یک تطابق می‌دهند. بنابراین یک رنگ‌آمیزی درست، معادل افراز کردن گراف به تطابق‌های جدا از هم است.
اگر اندازهٔ تطابق بیشینهٔ یک گراف کوچک باشد، آن‌گاه تعداد تطابق‌های لازم برای پوشاندن تمام یال‌های گراف زیاد است. به بیان رسمی‌تر، اگر یک گراف دارای m یال باشد و حداکثر β یال متعلق به یک تطابق بیشینه باشند، آن‌گاه هر رنگ‌آمیزی یالی گراف حداقل نیاز به m/β رنگ متفاوت دارد. برای مثال، گراف ۱۶-رأسی در تصویر روبه‌رو {{{1}}} یال دارد. در این گراف، تطابق کامل وجود ندارد زیرا اگر رأس وسط تطبیق داده شود، رأس‌های تطبیق داده نشده باقی‌مانده در سه مؤلفهٔ همبندی متفاوت با ۴، ۵، و ۵ رأس جای می‌گیرند و مؤلفه‌های با تعدادرأس فرد تطابق کامل نخواهند داشت. برای این گراف تطابق بیشینه‌ای با ۷ یال موجود است، پس β = ۷. بنابراین، تعداد رنگ‌های لازم برای رنگ‌آمیزی یالی حداقل ۲۴/۷ خواهد بود و چون تعداد رنگ‌ها باید عدد درستی باشد، حداقل به ۴ رنگ نیاز است.
برای یک گراف منظم از درجهٔ k که تطابق کامل ندارد، می‌توان از این کران پایین استفاده کرد و نشان داد حداقل k + ۱ رنگ نیاز است. به‌طور خاص، این گفته برای گراف‌های منظم با تعداد فردی رأس (مانند گراف‌های کامل فرد) درست است؛ برای این گراف‌ها، طبق لم دست دادن (hankshaking lemma)، k باید عددی زوج باشد. اما نامساوی χ′ ≥ m/β کاملاً شاخص رنگی هر گراف منظمی را توضیح نمی‌دهد، زیرا گراف‌های منظمی وجود دارند که تطابق کامل دارند اما k-رنگ‌پذیر-یالی نیستند. برای مثال، گراف پترسن منظم است با m = ۱۵ یال و β = ۵ یال در تطابق کامل، ولی ۳-رنگ‌آمیزی-یالی ندارد.
رابطه با درجه > قضیهٔ ویزینگ

عدد رنگی یالی یک گراف k رابطهٔ نزدیکی با بیشینه درجهٔ آن گراف Δ(G)، بیشترین تعداد ممکن یال مجاور به هر رأسی از آن گراف، دارد. واضحاً χ′(G) ≥ Δ(G) زیرا اگر Δ یال متفاوت همگی به یک رأس برسند، آن‌گاه همهٔ آن‌ها باید رنگی متفاوت از دیگری داشته باشند و این امر هنگامی ممکن است که حداقل Δ رنگ متمایز برای نسبت دادن به آن‌ها وجود داشته باشد. قضیهٔ ویزینگ (نامیده شده به خاطر ودیم جی ویزینگ که این قضیه را در ۱۹۶۴ اثبات و منتشر کرد) بیان می‌کند که این مرز تقریباً دو طرفه است، عدد رنگی یالی یا برابر Δ(G) است یاΔ(G) + ۱. وقتی χ′(G) = Δ(G) گراف G از کلاس ۱ و در غیر این صورت از کلاس ۲ خوانده می‌شود.
تمام گراف‌های دوبخشی از کلاس ۱ هستند، و تقریباً تمام گراف‌های تصادفی نیز از کلاس ۱ هستند. اما به‌طور کلی مسئلهٔ تشخیص این که گرافی از کلاس ۱ هست یا نه، ان‌پی کامل است.
ویزینگ (۱۹۶۵) ثابت کرد که گراف‌های مسطح با بیشینه درجهٔ حداقل هشت از کلاس ۱ هستند و حدس زد که برای گراف‌های مسطح با بیشینه درجهٔ هفت یا شش نیز درست باشد. از طرف دیگر گرافی‌های مسطحی با بیشینه درجهٔ دو تا پنج وجود دارند که از کلاس ۲ هستند. حدس گفته شده، پس از آن برای گراف‌های مسطح با بیشینه درجهٔ هفت اثبات شده‌است. گراف‌های مسطح مکعبی بدون پل همگی از کلاس ۱ هستند، که این مسئله معادلی از قضیهٔ چهاررنگ است.
رابطه با درجه > گراف‌های منتظم

۱-عامل-بندی از یک گراف k-منتظم، یک افراز از یال‌های گراف به تطابق‌های کامل است، که معادل k-رنگ‌آمیزی-یالی گراف است. یعنی یک گراف ۱-عامل-بندی دارد اگر و فقط اگر از کلاس ۱ باشد. در یک حالت خاص، یک ۳-رنگ‌آمیزی-یالی از از یک گراف مکعبی (۳-منتظم) گاهی رنگ آمیزی تیت نامیده می‌شود.
هر گراف منتظمی ۱-عامل-بندی ندارد، مانند گراف پترسن. در حالت کلی snarkها به گراف‌هایی گفته می‌شود که مانند گراف پترسن، ۳-منتظم و از کلاس ۲ هستند.
بنا به قضیهٔ کوئینگ (۱۹۱۶) هر گراف دو بخشی منتظم یک ۱-عامل-بندی دارد. این قضیه قبلاً به عنوان projective configurations مطرح شده بود و توسط ارنست استینیتز ثابت شد.
رابطه با درجه > گراف‌های چندگانه

برای گراف‌های چندگانه، که در آن‌ها ممکن است چند یال موازی دو رأس را چندبار به هم متصل کنند، نتیجه‌های مشابه به قضیهٔ ویزینگ ولی ضعیف‌تر از آن، عدد رنگی یالی گراف χ′(G) را به بیشینه درجه Δ(G) و چندگانگی گراف μ(G) که بیشترین تعداد یال‌های موازی بین هر دو رأس از گراف را نشان می‌دهد، مربوط می‌کند. ساده‌ترین مثال برای نشان دادن این که قضیهٔ ویزینگ را نمی‌توان برای گراف‌های چندگانه تعمیم داد،گراف شانون است: گرافی چندگانه با سه رأس و سه دسته از یال‌های موازی، هر دسته به تعداد μ(G) یال، که هر سه زوج از رأس‌ها را به هم متصل می‌کنند. در این مثال، Δ(G) = ۲μ(G) (هر رأس به دو دسته از سه دسته یال‌های موازی متصل است) ولی عدد رنگی یالی گراف برابر ۳μ(G) است (در کل ۳μ(G) یال وجود دارد که هر دو تایی از آن‌ها مجاورند پس رنگ هر کدام از یال‌ها باید با بقیه متفاوت باشد). شانون(۱۹۴۹) در یک نتیجه که بعدها الهام‌بخش ویزینگ شد، نشان داد که بدترین حالت برای هر گراف چندگانه این است که χ′(G) ≤ (۳/۲)Δ(G). همچنین، برای هر گراف چندگانه G، χ′(G) ≤ Δ(G) + μ(G)، نامساوی‌ای که برای گراف‌های ساده (که μ(G) = ۱) به قضیهٔ ویزینگ منجر می‌شود.
الگوریتم‌ها

از آن جا که مسئلهٔ امتحان کردن این که گرافی از کلاس ۱ هست یا نه، ان‌پی کامل است، هیچ الگوریتمی از زمان چندجمله‌ای وجود ندارد که گرافی را با تعداد رنگ‌های بهینه رنگ‌آمیزی یالی کند. با این وجود الگوریتم‌هایی طرح شده‌اند که یک یا چندی از این شرط‌ها را ندارند: بعضی فقط روی زیرمجموعه‌ای از گراف‌ها کار می‌کنند، بعضی همیشه از تعداد بهینهٔ رنگ استفاده نمی‌کنند، یا بعضی همیشه در زمان چندجمله‌ای اجرا نمی‌شوند.
الگوریتم‌ها > رنگ‌آمیزی بهینهٔ دسته‌هایی از گراف‌ها

در مورد گراف‌های دوبخشی یا برخی گرافهای مسطح با بیشینه درجهٔ Δ، تعداد رنگ‌های بهینه دقیقاً برابر است. کول، اُست و شیرا (۲۰۰۱) نشان دادند که رنگ‌آمیزی یالی بهینهٔ این گراف‌ها را با زمان تقریباً خطی O(m log Δ) می‌توان پیدا کرد که m تعداد یال‌ها است. الگوریتم‌های ساده‌تر اما بعضاً کندتر توسط کول و هاپکرافت(۱۹۸۲) و آلن (۲۰۰۳) ارائه شدند. الگوریتم آلن (۲۰۰۳) با منتظم کردن گراف ورودی، بدون تغییر درجه و تغییر محسوس سایز گراف، شروع می‌کند: با ادغام کردم زوج‌هایی از رأس‌ها که عضو یک بخش هستند و سپس اضافه کردن تعداد کمی رأس و یال دیگر. سپس اگر درجه فرد است، آلن یک تطابق کامل در زمان تقریباً خطی پیدا می‌کند، به آن یک رنگ نسبت می‌دهد و آن را از گراف حذف می‌کند، که در نتیجه درجه زوج می‌شود. در نهایت، آلن یک مشاهده از گابو (۱۹۷۶) اعمال می‌کند، که با انتخاب کردن متناوب زیرمجموعه‌هایی از یال‌ها در یک تور اویلری از گراف، آن را به دو زیرگراف منتظم تقسیم می‌کند، که در نتیجه مسئلهٔ رنگ‌آمیزی به دو زیرمسئله تقسیم می‌شود، و الگوریتم این دو زیرمسئله را به صورت بازگشتی حل می‌کند. زمان کل این الگوریتم از O(m log m) است.
برای گراف‌های مسطح با بیشینه درجهٔ Δ ≥ ۷، تعداد رنگ‌های بهینه دقیقاً Δ است. با فرض Δ ≥ ۹ می‌توان یک رنگ‌آمیزی یالی بهینه در زمان خطی پیدا کرد (کول و کوالیک ۲۰۰۸).
الگوریتم‌ها > الگوریتم‌های دقیق

به راحتی می‌توان امتحان کرد که یک گراف را با یک رنگ یا دو رنگ می‌توان رنگ‌آمیزی یالی کرد یا نه. بنابراین اولین حالت غیربدیهی رنگ‌آمیزی یالی، امتحان کردن این است که گرافی ۳-رنگ‌آمیزی-یالی می‌شود یا نه. کوالیک(۲۰۰۹) نشان داد که می‌توان در زمان O(۱٫۳۴۴n) و با استفاده از حافظهٔ خطی، امتحان کرد یک گراف ۳-رنگ‌آمیزی-یالی دارد یا نه. با این که این زمان نمایی است، ولی بسیار بهتر و سریع‌تر از امتحان کردن تمام حالت‌های ممکن نسبت دادن رنگ‌ها به یال‌هاست. هر گراف ۲-همبند ۳-منتظم با n رأس، از O(۲n/۲) عدد ۳-رنگ‌آمیزی-یالی دارد، که تمام آن‌ها را می‌توان در زمان O(۲n/۲) به دست‌آورد (قدری کندتر از زمان لازم برای پیدا کردن یک رنگ‌آمیزی)؛ همانطور که گرگ کوپربرگ مشاهده کرد، گراف یک منشور بر یک n/۲-ضلعی رنگ‌آمیزی‌های بسیاری دارد، که نشان می‌دهد این حد و مرز محکم است.
با اعمال کردن رنگ‌آمیزی رأسی به گراف خط گراف ورودی، می‌توان هر گرافی با m یال را رنگ‌آمیزی یالی بهینه کرد، با زمان 2mmO(1) و حافظهٔ خطی یا زمانO(۲٫۲۴۶۱m) و حافظهٔ خطی (Björklund, Husfeldt & Koivisto 2009).
از آن‌جایی که رنگ‌آمیزی یالی حتی برای سه رنگ هم ان‌پی کامل است، بعید است که وقتی که بر حسب تعداد رنگ‌ها پارامتری شود، مهارشدنی با پارامتر ثابت باشد. با این وجود، برای پارامترهای دیگری مهارشدنی هست. در عمل، زو، ناکانو و نیشیزکی(۱۹۹۶) نشان دادند که برای گراف‌هایی با عرض درختی w، یک رنگ‌آمیزی بهینهٔ یالی در زمان O(nw(۶w)w(w + ۱)/۲) قابل محاسبه است، زمانی که بر حسب w فرانمایی است ولی برحسب تعداد رأس‌ها n فقط خطی است.
نمهاسر و پارک(۱۹۹۱) مسئلهٔ رنگ‌آمیزی یالی را به عنوان یک برنامهٔ عدد صحیح فرمول بندی کردند و تجربهٔ خود را در استفاده از یک حل کنندهٔ برنامه‌نویسی عدد صحیح برای رنگ‌آمیزی یالی گراف‌ها توضیح دادند. ولی آن‌ها هیچ بررسی پیچیدگی زمان و حافظه‌ای برای الگوریتمشان ارائه ندادند.
خصوصیات دیگر

یک گراف به صورت یکتا k-رنگ‌پذیر-یالی است اگر بدون درنظرگرفتن جایگشت رنگ‌ها فقط یک راه برای تقسیم یال‌ها به k کلاس رنگی وجود داشته باشد (بدون در نظر گرفتن k! جایگشت رنگ‌ها). برای k ≠ ۳ تنها گراف‌های به صورت یکتا k-رنگ‌پذیر-یالی، مسیر، دور و ستاره است. برای k = ۳ دیگر گراف‌ها نیز ممکن است به صورت یکتا k-رنگ‌پذیر-یالی باشند. اگرچه همه گراف‌های ۳-رنگ‌پذیر همواره دارای دقیقاً سه دور همیلتونی هستند اما برعکس این موضوع صادق نیست یعنی گراف‌هایی با سه دور همیلتونی وجود دارند که به صورت یکتا ۳-رنگ‌پذیر-یالی نیستند همانند گراف‌های تعمیم‌یافتهٔ پترسن G(۶n + ۳, ۲) برای n ≥ ۲. تنها گراف غیر مسطح ۳-رنگ‌پذیر-یالی G(۹٬۲) است و فرضیه‌ای وجود دارد که گرافی دیگر وجود ندارد.
(Folkman & Fulkerson 1969) دنباله غیر افزایشی m۱, m۲, m۳, ...ها از اعداد را بررسی کردند با این خصوصیت که یک رنگ‌آمیزی یالی مناسب از گراف G وجود دارد که در آن گراف mi یال با رنگ i-ام وجود دارد. آن‌ها مشاهده کردند که اگر دنبالهٔ P امکان‌پذیر باشد و در lexicographic order بزرگتر از دنبالهٔ Q با همان جمع باشد، دنباله Q نیز امکان‌پذیر است. اگر در lexicographic order داشته باشیم P> Q، دنباله P با تعدادی متناهی از مراحل می‌تواند به Q تبدیل شود. دراین مراحل از هریک از اعداد mi یکی کاسته می‌شود و به mj که i <j یکی افزوده می‌شود. به بیان رنگ‌آمیزی یالی، از رنگی شروع می‌کنیم که توسط P منتشر شده‌است. درهریک از مراحل رنگ‌های i و j در چرخه Kempe جابه‌جا می‌شوند. به‌طور مشخص هرگراف یک رنگ‌آمیزی یالی equitable دارد که در آن تعداد رنگ‌ها بهینه است و تعداد یال‌های هردورنگ متفاوت فقط یکی اختلاف داشته باشد.
قضیۀ De Bruijn Erdos خصوصیات رنگ‌آمیزی گراف‌های متناهی به گراف‌های نامتناهی نیز منتقل می‌شود. برای مثال قضیه‌های شانون و ویزینگ که مربوط به درجه گراف و chromatic index هستند را می‌توان به گراف‌های نامتناهی تعمیم داد.
(Richer 2011) مسئله پیدا کردن رسم گراف را برای گراف مکعبی با این خصوصیت که همه یال‌های رسم شده دارای یکی از سه slop متفاوت باشد و هیچ دویالی بر روی یک خط نباشند. اگر رسمی از K۳٬۳ وجود داشته باشد، slopها می‌تواند به عنوان رنگ‌ها در گراف ۳-رنگ‌پذیر استفاده شود. همانطور که Richer نشان می‌دهد گراف دو بخشی ۳-منتظم با رنگ‌آمیزی تایت داده شده را می‌توان اینگونه رنگ کرد اگروتنهااگر گراف ۳-همبند باشد. برای گراف غیرچندبخشی، شرایط کمی پیچیده‌تر است: یک رنگ‌آمیزی داده شده را می‌توان با رسم گراف نشان داد اگر bipartite double cover گراف
۳-همبند باشد و درصورتی که هریک از جفت یال‌های monochromatic را حذف کنیم بازهم حاصل گرافی غیردوبخشی باشد. این شرایط را ممکن است بتوان در زمان چندجمله‌ای بررسی کرد، اگرچه مسئله بررسی گراف ۴-رنگ‌شده‌ی-یالی ۴-منتظم با رسم ۴-slop دارای پیچیدگی زمانی NP-complete است.
همان‌گونه که شاخص رنگی به بیشترین درجه و بیشترین تعداد تطابق‌های گراف مرتبط است، به linear arboricity گراف G نیز مرتبط است که آن‌را با la(G) نشان می‌دهد کمترین تعداد جنگل‌های خطی است که یال‌های گراف قابل افراز به آن جنگل‌ها باشند. یک تطابق حالت خاصی از جنگل خطی است و هر جنگل خطی، ۲-رنگ‌پذیر است. بنابراین برای هر گراف G داریم: la(G) ≤ χ′(G) ≤ ۲ la(G). فرضیه Akiyama بیان می‌کند که  \mathop {\mathrm {la} } (G)\leq \left\lceil {\frac {\Delta +1}{2}}\right\rceil  و این باید از رابطهٔ 2 la(G) − ۲ ≤ χ′(G) ≤ ۲ la(G) تبعیت کند. برای گراف با حداکثر درجه سه، la(G) همیشه مقدار دو می‌گیرد و بنابراین داریم χ′(G) ≤ ۲ la(G) که این همان حد قضیهٔ ویزینگ است.
مسائل باز

جنسن و تافت(۱۹۹۵) لیستی از ۲۳ مسئلهٔ بار در رابطه با رنگ‌آمیزی یالی ارائه دادند. این لیست عبارت است از:
حدس گلدبرگ(۱۹۷۳) که شاخص رنگی و شاخص کسری داخل یک‌دیگر هستند، که اجازهٔ تخمین زدن شاخص رنگی درون یک رنگ در زمان چندجمله‌ای را نمی‌دهد.
چندین حدس از جیکوبسن و دیگران در ساختن گراف‌های بحرانی برای رنگ‌آمیزی یالی، گراف‌هایی از کلاس ۲ که هر زیرگرافی از آن‌ها یا بیشینه درجهٔ کمتر دارد یا از کلاس ۱ است. جیکوبسن در اصل حدس زد که تمامی گراف‌های بحرانی تعداد رأس‌هایشان فرد است، ولی این حدس بعدها به مرور رد شد. بسیاری از حدس‌های دیگری که این حدس را ضعیف می‌کنند، یا حد گذاشتن روی تعداد رأس‌های گراف‌های بحرانی و گراف‌های چندگانهٔ بحرانی، باز باقی‌مانده‌اند.
مسئلهٔ ویزینگ که مسئلهٔ دسته‌بندی بیشینه درجاتی است که برای گراف‌های مسطح کلاس ۲ ممکن هستند.
حدس زیرگراف کاملاً پر از ای. جی. دبلیو. هیلتون، بیانگر این که گراف‌هایی با درجهٔ حداقل n/۳ یا از کلاس ۱ هستند یا دارای زیرگرافی با بیشینه درجهٔ Δ برابر با گراف اصلی و تعداد فرد k رأس هستند، که تعداد یال‌های این زیرگراف بیشتر از Δ(k − ۱)/۲ است، و حدسی مشابه این حدس از Herbert Grötzsch و پاول سیمور در رابطه با گراف‌های مسطح به جای گراف‌هایی با درجهٔ زیاد.
حدسی از چتویند و هیلتون (که احتمالاً به کار گابریل آندرو دیراک برمی‌گردد) که گراف‌های منتظم با تعداد زوج n رأس و درجهٔ حداقل n/۲ از کلاس ۱ هستند.
حدسی از کلاد برگ و دی. آر. فالکرسن که گراف‌های چندگانهٔ ۶-منتظم که از دوتا کردن هر یال یک گراف سادهٔ ۳-منتظم بدون پل به دست آمده است، ممکن است با ۶ رنگ رنگ‌آمیزی یالی شوند.
حدسی از فیورینی و ویلسون که هر گراف مسطح بدون مثلث، به جز پنجهٔ K۱٬۳ به‌طور یکتا ۳-رنگ‌پذیر نیست.
یک حدس اخیر این است که اگر G گراف چندگانهٔ d-منتظم مسطح باشد، آن‌گاه d، G-رنگ‌پذیر است اگر و فقط اگر G، d-همبند یالی باشد. این قضیه می‌تواند به عنوان تعمیمی از قضیهٔ چهاررنگ باشد که d=۳. ماریا چادنوسکی، کاترین ادواردز و پاول سیمور ثابت کردند که یک گراف چندگانهٔ ۸-منتظم یک عدد رنگی یالی ۸ دارد.
ساختار هندسی یک ۷-رنگ‌آمیزی-یالی گراف کامل K۸. هر کدام از ۷ دستهٔ رنگ یک یال از رأس مرکزی به یکی از رأس‌های چندضلعی دارد که سه یال بر آن عمود است.
این گراف مسطح ۳-منتظم ۱۶ رأس و ۲۴ یال دارد، ولی در هر تطابق بیشینه فقط ۷ یال دارد. بنابراین برای هر رنگ‌آمیزی یالی آن به چهار رنگ نیاز است.
گراف چندگانهٔ شانون با درجهٔ شش، چندگانگی یال سه، که نیاز به نه رنگ در هر رنگ آمیزی یالی دارد.
گراف تعمیم‌یافتهٔ پترسن G(۹٬۲) که به صورت یکتا ۳-رنگ‌پذیر است. یال‌های یکی از سه دسته رنگ به صورت کمرنگ نشان داده شده‌اند. دو دسته یال با رنگ‌های دیگر یا از چرخش ۴۰ درجه‌ای یال‌های کمرنگ به دست می‌آیند یا می‌توان یال‌های دور همیلتونی که با رنگ تیره نشان داده شده‌اند را یکی در میان رنگ کرد.
یک طرح از گراف K۳٬۳ که سه دسته یال با رنگ‌های یکسان آن، به صورت خط‌های موازی نشان داده می‌شوند.
یک افراز گراف کامل دو بخشی K۴٬۴ به سه جنگل، که نشان می‌دهد arboricity آن سه است.
کالج سلطنتی دامپزشکی

| 0 | 1 |
| --- | --- |
شعار: لاتین: Venienti Occurrite Morbo
شعار به انگلیسی: Confront disease at onset
نوع: مدرسه دامپزشکی دولتی
بنیانگذاری شده: ۱۷۹۱؛ ۲۳۳ سال پیش (۱۷۹۱-خطا: زمان نامعتبر}}) (در سال ۱۹۴۹ بخشی از دانشگاه لندن شد)
موقوفه مالی: ۱۰٫۵ میلیون پوند (۲۰۲۱)
بودجه: ۱۰۶٫۰ میلیون پوند (۲۱–۲۰۲۰)
رئیس دانشگاه: آن، شاهدخت سلطنتی (دانشگاه لندن)
مدیر اجرایی: استوارت رید
دانشجویان: ۲٬۱۴۵ (۲۰۱۴/۱۵)
کارشناسی: ۱٬۶۳۵ (۲۰۱۴/۱۵)
تحصیلات تکمیلی: ۵۱۰ (۲۰۱۴/۱۵)
موقعیت: لندن و هرتفوردشر، بریتانیا
پردیس: شهری
تعلق ورزشی به: دانشگاه لندن Universities UK
وبگاه: www.rvc.ac.uk/
کالج سلطنتی دامپزشکی (به انگلیسی: Royal Veterinary College) یک مدرسه دامپزشکی واقع در لندن و یکی از مؤسسات عضو دانشگاه لندن است. در سال ۱۷۹۱ تأسیس شد و در سال ۱۹۴۹ به دانشگاه لندن پیوست. کالج سلطنتی دامپزشکی، قدیمی‌ترین و بزرگ‌ترین مدرسه دامپزشکی در بریتانیا است. و یکی از تنها ۹ مدرسۀ دامپزشکی در بریتانیا است که دانشجویان می‌توانند در آن تحصیل کنند تا دامپزشک شوند.
چاه هفتاد تومانی ۱

| چاه هفتادتومانی ۱ | چاه هفتادتومانی ۱ |
| --- | --- |
روستا: روستا
مختصات: ۲۸°۴۷′۳۱″ شمالی ۵۵°۲۳′۳۷″ شرقی﻿ / ﻿۲۸٫۷۹۱۹۴°شمالی ۵۵٫۳۹۳۶۱°شرقی﻿ / 28.79194; 55.39361: مختصات: ۲۸°۴۷′۳۱″ شمالی ۵۵°۲۳′۳۷″ شرقی﻿ / ﻿۲۸٫۷۹۱۹۴°شمالی ۵۵٫۳۹۳۶۱°شرقی﻿ / 28.79194; 55.39361
کشور: ایران
استان: کرمان
شهرستان: سیرجان
بخش: گلستان
دهستان: گلستان
جمعیت: ۱۰۶ نفر (سرشماری ۹۵)
چاه هفتادتومانی ۱ یا عبدالحسین اسلاملو روستایی در دهستان گلستان بخش گلستان شهرستان سیرجان استان کرمان ایران است.
جمعیت

بر پایه سرشماری عمومی نفوس و مسکن در سال ۱۳۹۵ جمعیت این مکان ۱۰۶ نفر (۳۳خانوار) بوده‌است.
| جمعیت تاریخی> سال | جمعیت تاریخی> جمعیت | جمعیت تاریخی> ±% |
| --- | --- | --- |
| ۱۳۸۵ | ۴۰ | —     |
| ۱۳۹۰ | ۲۶ | ۳۵٪− |
| ۱۳۹۵ | ۱۰۶ | ۳۰۷٫۷٪+ |
آوانگارد اوکراینی

زن روستایی اوکراینی، ولادیمیر بورلیوک، بین ۱۹۱۰ تا ۱۹۱۱
آوانگارد اوکراینی اصطلاحی است که در طیفی گسترده برای تغییرات و نوآوری‌هایی که در هنر اوکراین از پایان دهه ۱۸۹۰ تا میانه دهه ۱۹۳۰ میلادی توسط هنرمندان رخ داد، استفاده می‌شود. آوانگارد اوکراینی به‌طور کلی در مجسمه‌سازی، نقاشی، ادبیات، سینما، تئاتر، طراحی صحنه، طراحی گرافیک، موسیقی و معماری با آوانگارد بین اللملی همگام و موازی بود. از هنرمندان نامدار در آوانگارد اوکراینی می‌توان به کازیمیر ماله‌ویچ، الکساندر آرکیپنکو، ولادیمیر تاتلین، سونیا دولونه، واسیل یرمیلوف، الکساندر بوگومازوف، الکساندرا اکستر، دیوید بورلوک، وادیم ملر، و آناتول پتریتسکی اشاره کرد. همه این هنرمندان از منظر محل تولد، تحصیلات، زبان و سنت یا هویت ملی با شهرهایی نظیر کیف، خارکف، لویو و اودسا ارتباط نزدیکی داشتند. از اولین گروه هنرمندانی که برای معرفی خود از اصطلاح آوانگارد استفاده کردند، در سال ۱۹۲۵ میلادی در شهر خارکیف بود.
اصطلاح آوانگارد اوکراینی در رابطه با نقاشی‌ها و مجسمه‌سازی‌های دوران سانسورهای شوروی و در راستای گفتگوهایی که دربارهٔ نمایشگاه رؤیایی تاتلین می‌شد، بسیار مورد استفاده بود. این نمایشگاه که توسط مورخ هنر پاریسی، آندری ناکوف در لندن، ۱۹۷۳ جمع آوری شده بود، آثار هنرمندان اوکراینی نظیر واسیل یرمیلوف و الکساندر بوگومازوف را به نمایش گذاشت. اولین نمایشگاه بین‌المللی آوانگارد در اوکراین، که شامل هنرمندان فرانسوی، ایتالیایی، اوکراینی و روسی بود، در اودسا و کیف در سالن ایزدبسکی ارائه شد. این قطعات بعداً در سن پترزبورگ و ریگا به نمایش گذاشته شد. جلد «سالن ایزدبسکی ۲» (۱۹۱۰–۱۱م) حاوی آثاری انتزاعی از واسیلی کاندینسکی نیز بود.
گاه‌شمار

۱۹۰۸: نمایشگاه "Zveno" در کیف. آثاری از الکساندرا اکستر، دیوید بورلوک، ولادیمیر بورلیوک، یوگنی آگافونوف و ولودیمیر دنیسوف.
۱۹۰۹: نمایشگاه "نیلوفر آبی" در خارکیف. آثار یوجین آگافونوف، ماریا سینیاکووا و واسیل یرمیلوف.
۱۹۱۰: نمایشگاه "Salon Izdebsky 2" در اودسا و کیف. آثاری از الکساندرا اکستر، دیوید و ولادیمیر بورلیوک، و واسیلی کاندینسکی، در کنار قطعاتی از پیر بونارد، ژرژ براک، ام. ولامینک، ام. دنی، آ. ماتیس، آ. روسو، و پی سیگنیاک.
۱۹۱۰: "هایلیا"، یک انجمن اوکراینی-روسی از شاعران فوتوریسم، در چورنیاکا، منطقه خاووسکی، در جنوب اوکراین تأسیس شد. اعضا عبارت بودند از دیوید و ولادیمیر بورلیوک، وی. کامنسکی، الکسی کروچیونیخ، بندیکت لیوشیتس، ولادیمیر مایاکوفسکی، ولیمیر خلبنیکوف، و دیگر هنرمندان.
۱۹۱۳: میخایلو سمنکو در کیف گروه فوتوریستهای اوکراینی به نام "Quero" را تأسیس کرد.
۱۹۱۴: الکساندرا اکستر – همراه با هموطنان اوکراینی خود مانند آرچیپنکو، ولادیمیر بارانوف-روسینه، کازیمیر مالویچ، وادیم ملر و برادران بورلیوک، نمایشگاهی با نام Société des Artistes Indépendants در پاریس گذاشتند و همچنین در کنار آرچیپنکو، در نمایشگاهی با نام Esposizione Libera Futurista Internazionale در رم ایتالیا شرکت کرد.
۱۹۱۴: الکساندرا اکستر و الکساندر بوگومازوف گروهی از هنرمندان کوبو-فوتوریست به نام "کولتسو" را در کیف برپا کردند.
۱۹۱۷: گروه هنری "اتحادیه هفت" در خارکیف تأسیس شد. اعضا شامل بوریس کوساروف، گئورگی تساپوک، ولودیمیر بوبریتسکی و نیکولای کالمیکوف بودند.
۱۹۲۴: مؤسسه هنر کیف (KHI); اعضا شامل الکساندر بوگومازوف، وادیم ملر، ویکتور پالموف، کازیمیر مالویچ، و ولودیمیر تاتلین بودند.
۱۹۲۵: انجمن هنری و مجله "Avangarde" در خارکیف، توسط وارلین پولیشچانک و واسیل یرمیلوف تأسیس شد.
۱۹۲۵: انجمن هنر انقلابی اوکراین (ARMU) در کیف تأسیس شد. اعضای آن عبارت بودند از میخایلو بویچوک، الکساندر بوگومازوف، ویکتور پالموف، واسیل یرمیلف و وادیم ملر.
۱۹۲۷: اتحادیه هنرمندان مدرن اوکراین (OSMU) در کیف تأسیس شد. ویکتور پالموف، آناتول پتریتسکی و پاول گولوبییتنیکوف از اعضای آن بودند.
۱۹۲۷: انجمن هنری و مجله‌ای با نام "نسل جدید" توسط ام. سمنکو، نینا ژنکلر، وادیم ملیر، lآناتول پتریتسکی و جیو اشکاروپی در خارکیف تأسیس شد.
هنرمندان > سینما

الکساندر داوژنکو
هنرمندان > نقاشان

Yevgeny Agafonov
الکساندر بوگومازوف
الکساندرا اکستر
میخایلو بویچوک
ولادیمیر بورلیوک
دیوید بوربلیوک
سونیا دولونه
Oleksandr Hnylytskyi
کازیمیر ماله ویچ
وادیم ملر
ویکتور پالموو
اوکسانا پاولنکو
واسیلی سدلیار
ماریا سینیاکووا
ولادیمیر تاتلین
واسیل یرمیلوف
Kostiantyn Piskorskyi
هنرمندان > مجسمه سازان

الکساندر آرکیپنکو
ایوان کاوالیدزه
هنرمندان > نمایشنامه نویسان

لیس کورباس
هنرمندان > طراحان صحنه

میخایلو اندرینکو-نچینایلو
وادیم ملر
آناتول پتریتسکی
هنرمندان > نویسندگان

والرین پولیشچانک
میخایلو سمنکو
جیو اشکارویی
واسیل یرمیلوف جلد مجله «آوانگارد»، ۱۹۲۹ میلادی
ترکیب‌بندی والاگرایانه ۱۹۱۶ م. در مالکیت مجموعه‌دار شخصی اثر کازیمیر ماله ویچ
خیابان در پودیل، الکساندر بوگومازوف، ۱۹۱۲م.
الکساندرا اکستر، طرحی از مجموعه مجموعه لوبانوف-روستوفسکی ۱۹۲۴م.
کامیتا، توکوشیما

| کامیتا 上板町 | کامیتا 上板町 |
| --- | --- |
شهر: شهر
  پرچم:   پرچم
موقعیت کامیتا در استان توکوشیما: موقعیت کامیتا در استان توکوشیما
کشور: ژاپن
منطقه: شیکوکو
استان: استان توکوشیما
ناحیه: Itano
مساحت: مساحت
 • کل: ۳۴٫۵۱ کیلومتر مربع (۱۳٫۳۲ مایل مربع)
جمعیت (۲۰۰۳): جمعیت (۲۰۰۳)
 • کل: ۱۳۱۲۶
 • تراکم: ۳۸۰/کیلومتر مربع (۹۹۰/مایل مربع)
منطقهٔ زمانی: یوتی‌سی +۹ (زمان)
وبگاه: www.townkamiita.jp
کامیتا (上板町, Kamiita-chō؟) یک منطقهٔ مسکونی در ژاپن است که در استان توکوشیما واقع شده‌است. کامیتا ۱۳٬۱۲۶ نفر جمعیت دارد.
زنان در نیجر

| 0 | 1 |
| --- | --- |
سه زن در نیجر در سال ۱۹۹۷.: سه زن در نیجر در سال ۱۹۹۷.
شاخص نابرابری جنسیتی: شاخص نابرابری جنسیتی
ارزش: ۰٫۶۱۱ (۲۰۲۱)
رُتبه: ۱۵۳ از ۱۹۱
مرگ مادر (در هر ۱۰۰٬۰۰۰): ۵۹۰ (۲۰۱۰)
سهم زنان در دولت‌ها: ۱۵٪ (۲۰۱۷)
زنان بالای ۲۵ سال با آموزش متوسطه: ۲٫۵٪ (۲۰۱۲)
زنان کارمند و شاغل: ۶۹٪ (۲۰۱۷)
گزارش جهانی فاصله جنسیتی: گزارش جهانی فاصله جنسیتی
ارزش: ۰٫۶۳۵ (۲۰۲۲)
رُتبه: ۱۲۸ از ۱۴۶ از مجموعِ ۱۴۴
زنان در نیجر (به انگلیسی: Women in Niger) به جمعیتی تعلق دارند که ۹۸ درصد آن پیروان اسلام هستند. قوانینی که توسط دولت نیجر برای حمایت از حقوق زنان نیجریه ای تصویب می‌شود، اغلب بر اساس اعتقادات مسلمانان است. زنان نیجری در گروه‌های قومی مختلفی قرار می‌گیرند. در میان بزرگ‌ترین گروه‌های قومی می‌توان به زنان هاوسا، زنان فولانی، زنان زارما – سونگهای و زنان توارگ اشاره کرد. زنان هوسا نیجر را می‌توان با لباس‌هایشان شناسایی کرد که در آن لفاف‌هایی به نام عبای ساخته شده از پارچه‌های رنگارنگ با بلوز، کراوات سر و شال همسان می‌پوشند.
یک تعطیلات عمومی در نیجر که به عنوان روز ملی زنان نیجریه با عنوان Journée nationale de la femme nigérienne نیز شناخته می‌شود و هر ساله در ۱۳ مه برگزار می‌شود. این روز به یاد راهپیمایی سال ۱۹۹۲ توسط زنان در نیامی در طول دوره کنفرانس ملی است که خواستار مشارکت بیشتر زنان در نهادهای ملی بودند. این روز در ۲۵ نوامبر ۱۹۹۲ به یادبود ملی تبدیل شد.
پیشینه فرهنگی

نیجر کشوری در غرب آفریقا است. این کشور در سال ۱۹۶۰ از استعماری فرانسه مستقل شد و تا سال ۱۹۹۱ توسط حکومتی تک حزبی و نظامی اداره می‌شد. بیشتر مناطق این کشور دارای آب و هوای گرم، خشک و بیابانی است. این کشور تقریباً ۲۰ میلیون نفر جمعیت دارد. اکثراً یک جامعه روستایی است و تقریباً همه مردم اسلام دارند.
ازدواج و خانواده

مادر شدن در نیجر عوارض زیادی دارد. به دلیل عوامل اقتصادی، ناکافی بودن مراقبت‌های بهداشتی و شیوه‌های سنتی، زنان تا زمانی که اولین فرزند خود را به دنیا می‌آورند، در شرایط بدی قرار دارند.