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

((x1)=1, ((x2)=2,…, ((xr)=r, ((xr+1)=1,…,((xn)=1+(n-1)mod r.

Очевидно, що розфарбування ( врівноважене. Візьмемо довільну вершину v(V. Якщо v - вершина одного з графів R1(R2, R3(R4,…, Rt-1(Rt, то у відповідному графі на відстані ( r від вершини v знаходяться вершини усіх r кольорів. Якщо ж v - вершина одного з променів Rt+1, Rt+2,…, Rs , то d(v,x)
Якщо число t непарне, пофарбуємо вершини зірки R1(R2(R3 згідно з лемою 1.1. Позначимо через m число вершин зірки R1(R2(R3, m=ra+b, 0(b
Для натурального числа r>1 дерево, що має принаймні r вершин, назвемо r-критичним, якщо після видалення будь-якого його ребра хоча б одне з двох утворених дерев має менше ніж r вершин. Нагадаємо, що діаметром скінченного зв'язного графу називається максимальна відстань між його вершинами.

Лема 3. В r-критичному дереві Gr(V,E) діаметра d( r-1 знайдеться вершина x, після видалення якої дерево розпадається на піддерева з числом вершин
Доведення. Виберемо вершини v0,vd( V, такі що d(v0,vd )=d. Нехай v0,v1, …,vd - найкоротший шлях від вершини v0 до вершини vd. Для кожного числа i({1,2,…,d} позначимо через Ti дерево з коренем vi, утворене видаленням з Gr(V,E) ребра (vi-1,vi). Виберемо мінімальне число m({1,2,…,d}, таке що дерево Tm має
Лема 4. Для кожного r-критичного дерева Gr(V,E) існує врівноважене r-розфарбування множини вершин V, індекс якого не перевищує r.

Доведення. Якщо діаметр d дерева ( r, то будь-яке r-розфарбування множини вершин V має індекс ( r. Для d >r виберемо вершину x, що задовольняє лему 1.3. Позначимо через y1,y2,…,ys усі суміжні з x вершини дерева. Розглянемо дерева T(y1), T(y2),…,T(ys) з коренями y1,y2,…,ys, одержані видаленням ребер (y1,x),(y2,x),…,(ys,x). В кожному з них виберемо по одній вершині zi, що найбільше віддалена від кореня. Позначимо через R1,R2 ,…,Rs підграфи графу Gr(V,E), що визначаються найкоротшими шляхами від x до z1,z2,…,zs. Тоді граф S=R1(R2(…(Rs є зіркою радіуса ( r-1.

Припустимо, що серед променів зірки S є принаймні два довжини ( r/2. За лемою 1.2 існує врівноважене r-розфарбування індексу ( r множини вершин зірки S. Продовжимо його довільним чином до врівноваженого розфарбування ( множини S. Візьмемо довільну вершину v(V, v(x і виберемо піддерево T(yi), вершиною якого є v. Оскільки число вершин дерева T(yi) менше r, то B(zi,r)(B(v,r). Оскільки куля B(zi,r) містить точки усіх r кольорів зірки S, то розфарбування ( має індекс( r.

Припустимо, що лише один промінь зірки S, скажімо R1, має довжину ( r/2. Серед променів R2,R3,…,Rs виберемо промінь, скажімо R2, найбільшої довжини. Оскільки d > r, то граф R1(R2 має ( r вершин. Занумеруємо їх в порядку розташування від кінця променя R2 до кінця променя R1 і продовжимо цю нумерацію довільним способом на всю множину V. Упорядковану послідовність x1,x2,…,xn вершин множини V розфарбуємо за правилом ((xi )=1+(i-1) mod r. Врівноваженість розфарбування ( очевидна. Візьмемо довільну вершину v(V. За означенням розфарбування ( в кулі B(v,r) містяться r різнокольорових точок графа R1(R2. Отже, індекс розфарбування ( не перевищує r.

Для підмножини A множини вершин графа Gr(V,E) позначимо через Gr[A] граф з множиною вершин A і множиною ребер E((A(A).

Лема 5. Нехай Gr(V,E) - скінченний зв'язний граф, r - натуральне число і множину вершин V розбито на підмножини V1,V2,…,Vk, так, що всі графи Gr[V1],Gr[V2],…,Gr[Vk] зв'язні і допускають врівноважені r-розфарбування (1,(2,…,(k , індекс яких не перевищує r. Тоді існує врівноважене r-розфарбування ( множини V, індекс якого теж не перевищує r.

. Змінюючи нумерацію кольорів, можна вважати, що (i(xij)=1+(j-1)modr для всіх i({1,2,…,k}, j({1,2,…,mi}. Запишемо вершини множини V у послідовність



і для i-го члена v цієї послідовності покладемо ((v)=1+(i-1)mod r .

Доведення теореми 2. Для r=1 теорема очевидна. Припустимо, що r>1. Ми можемо замінити граф його кістяком і вважати, що Gr(V,E) - дерево. Послідовним видаленням ребер розіб'ємо множину V на підмножини V1,V2,…,Vk так, що Gr[V1],Gr[V2],…,Gr[Vk] - r-критичні дерева. Застосуємо леми 1.4 і 1.5.

Приклад 2. Нехай G - скінченна група з одиницею e, S(G, |S|=r, S=S-1, e(S. Розглянемо граф Келі Cay(G) групи G з множиною вершин G і множиною ребер {(x,y): x,y(G, x(y, xy-1(S}. Застосуємо теорему 2 до кожної зв'язної компоненти графа Cay(G), а потім - лему 5. Отримаємо таке твердження.

Існує врівноважене розбиття групи G=A1(A2(…(Ar, таке що G=SrAi для всіх i({1,2,…,r}.

Якщо S - підгрупа групи G, то вказати таке розбиття дуже просто: кожен лівий суміжний клас групи G за підгрупою S пофарбуємо кольорами {1,2,…,r} і позначимо через A1,A2,…,Ar однокольорові підмножини. Отже, теорему 2 можна розглядати як аналог для графів теореми Лагранжа про розклад групи на суміжні класи за підгрупою.

У зв'язку з теоремою 1 виникає таке питання. Чи можна множину вершин скінченного зв'язного графа розбити на підмножин індексу 1 за умови, що локальний ступінь кожної вершини досить великий? Нагадаємо, що локальний ступінь вершини - це кількість ребер, що виходять з цієї вершини. Уточнимо це питання. Чи для кожного натурального числа r знайдеться натуральне число f(r), таке що будь-який скінченний зв'язний граф з локальними ступенями вершин ( f(r) можна розфарбувати r кольорами так, що кожна куля радіуса 1 містить вершини усіх r кольорів?

Числа f(1), f(2) визначаються теоремою 1: f(1)=f(2)=1. Наступний приклад показує, що числа f(3) взагалі не існує.

Приклад 3. Для кожного натурального числа m покладемо Xm={1,2,…,3m} і позначимо через Ym сім'ю усіх m-підмножин множини Xm. Розглянемо граф Grm з множиною вершин Vm = Xm( Ym і множиною ребер Em, де (x,y)(Em тоді і тільки тоді, коли x(Xm , y(Ym і x(y. Зауважимо, що локальний ступінь кожної вершини графа Grm не менший за m. Зафіксуємо довільне 3-розфарбування (: Vm \x2192 {1,2,3} . Оскільки |Xm=3m|, то знайдеться однокольорова m-підмножина у множини Xm. Значить, |((B(y,1))|<3.