Розкладність графів. Хроматичні і калейдоскопічні числа, Детальна інформація

Наступний приклад показує, що верхня оцінка (і) в теоремі 6.5 є точною.

Приклад 1. Побудуємо зв'язний граф Gr з n вершинами і m ребрами, для якого ((Gr)=( , де

) ( 2].

(9)

Очевидно, що число m ребер зв'язного графа з n вершинами задовольняє нерівності

n-1( m( n(n-1)/2.

Враховуючи (9) одержуємо нерівності

(( n, (((-1) /2 ( m, n- ( ( m-(((-1) /2 .

Граф Gr будуємо так: виберемо довільну вершину повного графа з ( вершинами і приєднаємо до неї ланцюг з n-( вершинами і n-( ребрами, а решту

m-(((-1) /2 -(n-()

ребер визначаємо довільним чином. Оскільки граф Gr містить повний граф з ( вершинами, то ((Gr)( ( . З нерівності (і) випливає, що ((Gr)( (. Отже, ((Gr)= (.

Розглянемо довільний граф Gr(V,E). Калейдоскопічним число графа Gr(V,E) називається найменший кардинал k(Gr), для якого існує розфарбування (: V( k(Gr), таке що в кожній кулі B(x,1), x(V немає двох однокольорових вершин. Зрозуміло, що ((Gr)+1( k(Gr) (. |V|. Побудуємо допоміжний граф Gr'(V,E'), де E' - множина усіх пар різних вершин із V, відстань між якими в графі Gr(V,E) не перевищує 2.

Задача 3. Довести, що k(Gr)=((Gr').

Задача 4. Довести, що k(Gr)( ( (Gr)(((Gr)-1)+1.

Задача 5. Нехай Grn - цикл з n вершинами, n(3. Довести, що



Задача 6. Довести, що k (Tr)=( (Tr)+1 для кожного дерева Tr.

Задача 7. Довести, що однорідний граф Gr скінченного степеня k калейдоскопічний тоді і тільки тоді, коли k (Gr)=k+1.