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

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

Розв'яжемо цю нерівність відносно ( (Gr) і одержимо

/2.

Доведемо нижню оцінку (іі). Позначимо ( (Gr)=k. Назвемо відсутнім ребром (vq,vp) в графі Gr будь-яку упорядковану пару несуміжних вершин, а також усі пари (vq,vq). Очевидно, що кількість відсутніх ребер дорівнює n2 -2m. Зафіксуємо деяке мінімальне розфарбування графа Gr. Нехай Xi - множина усіх вершин кольору i, ni=|Xi|, i({1,2,…,k}. Оскільки усі вершини множини Xi попарно несуміжні, то загальне число відсутніх ребер, утворених лише вершинами з Xi , дорівнює ni2. Звідси випливає нерівність

( n2 -2m (1)

за додаткової умови

за умови (2) на множині цілих чисел. Для цього покладемо

ni = [n/k]+yi, l=n-[n/k]k,

(3)

де n/k - значення ni, що мінімізує функцію F за умови (2) на множині раціональних чисел. Очевидно, що

за умови (4). Цей мінімум досягається, наприклад, при

y1=y2=…=yk-l=0, yk-l+1=…=yk=1.

Звідси випливає, що

p=n2/k+k(n/k-[n/k])(1+[n/k]-n/k),

(5)

де n2/k - мінімум функції F на множині раціональних чисел. Отже, нерівність (1) можна переписати у такому вигляді

k2(n/k-[n/k])(1+[n/k]-n/k)( (n2-2m)k-n2

(6)

З цієї нерівності випливає, що

((Gr)( ([(x0],

(7)

де x0 - корінь рівняння

x2(n/x-[n/x])(1+[n/x]-n/x)( (n2-2m)x-n2

(8)

що лежить на відрізку від 1 до n.

Досліджуючи поведінку лівої та правої частин рівняння (8), можна показати, що [n/x0]=[n/x1], де x1 - корінь рівняння

(n2-2m)x-n2=0.

Обчислимо [n/x1] і поставимо його в (8). Одержимо лінійне рівняння відносно x, з якого знаходимо

.

Враховуючи (7), одержуємо оцінку (іі).