е деякі нерівності для хроматичного числа. Взагалі кажучи, ці нерівності досить грубі, але для кожного з них можна вказати графи, для яких нерівність дає хорошу (верхню чи нижню) оцінку хроматичного числа. Тому всі відомі оцен?? і можуть бути застосовані до даного графу, а потім з них слід вибрати найкращу.
У загальному випадку хроматичної число не визначається спектром. Більше того, Хоффман довів, що в певному сенсі є суттєва невідповідність між спектром і хроматичним числом графа.
Перейдемо до викладу деяких теорем, що відносяться до даної теми. Почнемо з теореми, що належить Уілф.
Теорема 2.16. Нехай? (G) - хроматичної число, а r - індекс (рівний максимальному власному значенням) зв'язного графа G. Тоді
? (G)? r + l. (2.15)
Рівність має місце тоді і тільки тоді, коли G - повний граф або простий цикл непарної довжини.
Доказ. Нехай dmin (H) і dmax (H) означають найменшу і найбільшу ступінь вершини в графі Н і нехай? L (H) - індекс графа Н. Оскільки (G) - хроматичної число графа G, то існує породжений підграф Н графа G, для якого dmin (Н? (G) - 1. Отримуємо
dmin (H)? ? (G) - 1 (2.16)
а, значить, і (2.15). Нехай у (2.15), а отже, і в (2.16) має місце рівність. Тоді з? L (G) =? 1 (Н) слід G=H, оскільки G зв'язний. Далі,? 1 (G)=dmin (G), звідки випливає по теоремі 2.8, що G регулярний. Значить, (G)=1 + r=1 + dmax (G). З відомої теореми Брукса слід тепер, що G - або повний граф, або простий цикл непарної довжини. Це і завершує доказ.
Перш ніж перейти до узагальнення цієї теореми, введемо кілька визначень.
Граф G називається k-виродженим для деякого цілого невід'ємне k, якщо dmin (H)? k для кожного породженого подграфа H графа G. Число вершинного розбиття (G) графа G є найменше число множин, на які може бути розбита безліч вершин графа G так, що кожне таке безліч при цьому породжує k-вироджений підграф графа G. Оскільки 0-вирожденние графи - це в точності цілком незв'язні графи, то 0 (G) - хроматичної число графа G. 1 (G) називається вершинної деревних графа G, оскільки 1-вироджені графи є лісами.
Можна довести, що кожен граф G містить породжений підграф H з dmin (H)? (k + 1) ((G) - 1). На цій основі абсолютно аналогічно тому, як це було зроблено в попередньому випадку, може бути доведена наступна теорема.
Теорема 2.17. Для будь-якого графа G з індексом r і будь-якого неотрицательного цілого k
Для доказу наступної теореми наведемо без доведення лемму.
Лемма 2.2. Нехай А - дійсна симетрична матриця порядку n і - розбиття множини {1, ..., n} на непорожні підмножини. Akk означає підматрицю матриці А з індексами рядків і стовпців з. Тоді, якщо k=1, .... t,
(2.17)
де? f (X), i=1, 2, ... - власні значення матриці X в порядку спадання.
Теорема 2.18. Якщо r (r? 0) і q - найбільше і найменше власні значення графа G, то його хроматичної число задовольняє нерівності
(2.18)
Доказ. Нехай? (G)=t і вершини графа G позначені числами 1, ..., n. Тоді існує розбиття таке, що кожен підграф графа G, породжений підмножиною не містить ребер. При ik=0 (k=1, ..., t) з (2.17) для власних значень=q графа G отримуємо
(2.19)
Так як, то (2.18) випливає з (2.19). Це і завершує доказ теореми.
Зауважимо, що з (2.19) можна отримати більше інформації про хроматическом числі, ніж з (2.18). Дійсно, (2.19) дає кордон
З наступної теореми нижня межа для хроматичного числа виходить інший.
Теорема 2.19. Якщо G - граф з n вершинами, індексом r і хроматичним числом X (G), то
Доказ. Розглянемо хроматичний многочлен к-повного графа. Многочлен має єдиний позитивний корінь - простий. Дійсно, повні многодольний графи є саме такими зв'язковими графами з простим позитивним власним значенням. Значить, для х gt; 0 тоді і тільки тоді, коли х ?? 1. Тепер розглянемо значення
,? gt; 0, (2.20)
Припустимо, що ni можуть брати позитивні дійсні значення. Тоді (2.20) досягає свого найбільшого значення, коли всі ni рівні. Дійсно, якщо ni? Nj, то, припускаючи, що) і не змінюючи всіх інших значень, приходимо до висновку, що сума (2.20) є зростаючою. Для приватного значення сума (2.20) дорівнює 1 тоді, коли ni рівні Тому, коли nt позитивні цілі числа, то вираз неотрицательно і, отже,
(2.21)
Тут рівність справедливо лише у випадку, коли граф регулярний.
Таким чином, доведений наступний результат.
Лемма 2.3. Індекс r графа Kn ..... nk задовольняє нерівності
де
Теорема 2.20. Якщо - число власних значень графа G, не великих - 1, то існує функція f така, що
Теорема 2.21. Якщо - власні значення графа G, a р +, p_, p- числа влас...
