Резюме: ръб оцветяване. Проблеми на графики с цветни ръбове и получените свойства. Проблемът на несвързаните триъгълници със страни от един цвят.
ръб оцветяване
Графиката се нарича край - правдоподобен. ако неговите краища могат да бъдат цветни бои, така че няма две съседни ребра ще бъдат от един и същи цвят. Ако графиката ръба -colorable, но не е -colorable ръб, той се нарича хроматичната клас или хроматичната индекс. или край хроматичната брой на графика. Той използва за запис. Картината показва графиката за това.
Ясно е, че ако на максимална степен на върховете е равна, а след това. Следващият резултат е известна като теорема Vizinga осигурява точни прогнози за хроматичната диаграма клас. Доказването на това теорема може да се намери в руда (руда О. Проблемът с четири цвята. Academic Press, New York, 1967).
Теорема 7.1. (Wiesing, 1964) Нека графиката без бримки, максималната степен на върха след това.
Задачата е да се установи какви са графики хроматичната клас, и който не е решен. Въпреки това, в някои специални случаи, резултатите са лесни. Например, или 3, в зависимост от това дали равна или нечетен и когато. Хроматичната класове пълни графики и цялостни двустранни графики са изчислени, твърде лесно.
Свързани статии