Розкладність графів. Врівноважені розбиття скінченних графів, Детальна інформація

Доведення. Припустимо для визначеності, що r1( r2( r3. Запишемо вершини променів R1, R2, R3 у порядку їх розташування від початку променя до його кінця

.

Якщо r=2, то r1=r2=r3=1 і будь-яке врівноважене 2-розфарбування має індекс 2.

Припустимо, що r>2, r=3r'+j, 0( j<3. Подамо число r у вигляді суми r = a+b+c, a( b( c=r'.

Розглянемо послідовність r вершин



від центра x вже знаходяться вершини всіх r кольорів. Для того щоб продовжити це часткове розфарбування ( на всю множину вершин V розглянемо два випадки.

. Непофарбовані вершини зірки запишемо у такому порядку



і пофарбуємо їх періодично зліва направо, починаючи з кольору a+b+1. Точніше, колір i-го члена v цієї послідовності визначається за формулою



від x знайдуться точки усіх r кольорів. Це і означає, що індекс розфарбування ( не перевищує r.

. Продовжимо розфарбування ( на множину

xa, xa+1 , …, xa+b-1, yb+1, yb+2,…, yb+c, zc+1, zc+2,…, zc+a

за таким правилом

((xa)=((y1), ((xa+1)=((y2),…,((xa+b-1)=((yb),

((yb+1)=((z1), ((yb+2)=((z2),…,((yb+c)=((zc),

((zc+1)=((x), ((zc+2)=((x1),…,((zc+a)=((xa-1),

містять відповідно

a+b+r-r1, b+c+r-r2+1, a+c+r-r3

розфарбованих різнокольорових вершин. Завершимо розфарбування за таким правилом

)=((zc),

)=((xa),

)=((yb),

Оскільки на останньому етапі розфарбування кожен колір використано не більше одного разу, то розфарбування ( врівноважене. Оскільки на відстані ( r від кожного кінця променів R1, R2, R3 розташовані вершини усіх r кольорів, то індекс розфарбування ( не перевищує r.

Лема 2. Нехай r - натуральне число ( 2, Gr(V,E) - зірка з центром x радіуса ( r-1, що містить принаймні два променя довжини ( r/2. Тоді існує врівноважене r-розфарбування індексу ( r множини V.

Доведення. Нехай R1, R2,…, Rt - промені довжини ( r/2, Rt+1, Rt+2,…, Rs - промені довжини < r/2,

Gr(V,E) = R1(R2(…(Rt(Rt+1(…(Rs.

Запропонуємо два способи розфарбування множини V в залежності від парності числа t.

Якщо число t парне, занумеруємо вершини дерева R1(R2 послідовними натуральними числами у порядку їх розташування від кінця променя R1 до кінця променя R2. Продовжимо нумерацію таким же способом на вершини дерева R3(R4, пропускаючи вже занумерований центр x і т. д. Отже, початковим відрізком натурального ряду вже занумеровано вершини дерева R1(R2(…(Rt. Продовжимо цю нумерацію довільним числом на решту вершин зірки Gr(V,E) і одержимо деяке упорядкування x1,x2,…,xn множини V. Пофарбуємо вершини x1,x2,…,xn кольорами {1,2,…,r} зліва направо за правилом