Розкладність графів. Калейдоскопічні графи

Однорідний граф Gr(V,E) скінченного степеня s називається калейдоскопічним, якщо існує розфарбування : V{0,1,,s}, таке що |(B(x,1))|=s+1 для будь-якого xV. В цьому разі розфарбування теж називається калейдоскопічним. Отже, калейдоскопічні графи – це графи, що допускають калейдоскопічне розфарбування. Дамо рівносильне означення: розфарбування : V{0,1,s} називається калейдоскопічним, якщо в кожній кулі одиничного радіуса немає двох однокольорових вершин.

З точки зору розкладності калейдоскопічні графи – це однорідні графи скінченого степеня, максимально розкладні відносно сім’ї всіх одиничних куль.

Розпочнемо дослідження калейдоскопічних графів з їх елементарних властивостей та прикладів. Далі запис a|b означає, що ціле число a є дільником цілого числа b.

Лема 1. Нехай Gr(V,E) – скінченний калейдоскопічний граф степеня s: V{0,1,s} – калейдоскопічне розфарбування. Тоді справедливі такі твердження:

(i)s+1/n;

(ii)|--1(0)|=|--1(1)|=…=|--1(s)|.

Доведення. Для кожного i{0,1,s} сім’я куль {B(x,1): x--1(i)} утворює розбиття множини вершин V. Оскільки |B(x,1)--1(i)|=1 , то

(s+1)|--1(i)|=|V|.

З цієї рівності випливають обидва твердження леми.

Приклад 1. Нехай Grn(Vn,En) – циклічний граф з n>2 вершинами. Припустимо що Grn(Vn,En) калейдоскопічний. Оскільки Grn – однорідний граф степеня 2, то 3|n за лемою 3.1(і). З іншого боку, якщо 3/n, то періодичне 3-розфарбування множини Vn є калейдоскопічним.

Приклад 2. Розглянемо п’ять правильних многогранників у просторі як скінченні графи і покажемо, що серед них калейдоскопічними є лише тетраедр, куб та ікосаедр. Очевидно, що кожне 4-розфарбування множини вершин тетраедра є калейдоскопічним. Зафіксуємо довільну вершину x куба і довільне 4-розфарбування кулі B(x,1). Далі, кожну вершину y' куба, симетричну до деякої вершини yB(x,1) відносно центра куба пофарбуємо кольором вершини y. Одержимо калейдоскопічне розфарбування куба. Аналогічне розфарбування виявляється калейдоскопічним і для ікосаедра. Оскільки октаедр має 6 вершин і є однорідним степеня 4, то він не є калейдоскопічним за лемою 3.1(і). Нарешті, додекаедр є однорідним графом степеня 3. Візьмемо довільний п’ятикутник, що є гранню додекаедра. Для будь-якого 4-розфарбування множини вершин додекаедра, знайдуться принаймні дві однокольорові точки на вказаній грані. Отже, одинична куля з центром в деякій вершині грані містить дві однокольорові вершини.

Лема 2. Нехай Gr(V,E) – скінчений однорідний граф степеня s, |V|=2m, XV. Припустимо, що існують розбиття V=V(0)V(1), |V(0)|=|V(1)|=m і натуральні числа p, q, для яких виконуються такі умови:

(i){B(x,1): xX} =V;

(ii)(s+1)|X|=2m;

(iii)s+1=p+q, p>q;

(iv)якщо xV(i), i{0,1}, то |B(x,1)V(i)|=p, |B(x,1)(V\V(i)|=q.

Тоді |XV(0)|=|XV(1)|.

Доведення. Позначимо k0=|XV(0)|, k1=|XV(1)|. З умов (і), (іv) випливають такі нерівності