Інваріант Колен де Вердьєра

Інваріа́нт Колен де Вердьєра — характеристика графа $\mu (G)$, визначена для будь-якого графа $G$, яку 1990 року ввів Шаблон:Iw2 в процесі дослідження кратності другого власного значення деяких операторів Шредінгера.

Визначення

Нехай $G=(V,E)$ — простий (без петель і кратних ребер) ациклічний граф. Без втрати загальності поіменуємо множину вершин у такий спосіб: $V=\{1,\dots ,n\}$. Тоді $\mu (G)$ — найбільший Шаблон:Iw2 будь-якої такої симетричної матриці $M=(M_{i,j})\in {ℝ}^{(n)}$, що:

• (M1) для будь-яких $i,j$, де $i\ne j$: $M_{i,j}<0$, якщо $\{i,j\}\in E$, і $M_{i,j}=0$, якщо $\{i,j\}\notin E$;
• (M2) $M$ має рівно одне від'ємне власне значення кратності $1$;
• (M3) не існує такої ненульової матриці $X=(X_{i,j})\in {ℝ}^{(n)}$, що $MX=0$, і що $X_{i,j}=0$ щоразу, коли $i=j$ або $M_{i,j}\ne 0$.

Класифікація відомих груп графів

З точки зору інваріанта Колен де Вердьєра, деякі добре відомі сімейства графів мають характерні особливості:

• $\mu (K_1)=0$, $\mu (K_n)=n-1$, $\mu (\overline{K_n})=1$ при $n>1$;
• Шаблон:Nobr тоді й лише тоді, коли G є лінійним лісом (лісом, у якому кожен компонент є шляхом, тобто інцидентність будь-якої вершини не більша від 2);
• Шаблон:Nobr тоді й лише тоді, коли G є зовніпланарним графом (усі вершини лежать на одній грані);
• Шаблон:Nobr тоді й лише тоді, коли G є планарним графом;
• Шаблон:Nobr тоді й лише тоді, коли G є незачеплено вклада́ним, тобто не існує двох циклів у G, для яких при відображенні на евклідів простір коефіцієнт зачеплення дорівнює нулю.

Ці ж групи графів проявляють свої відмінні риси і під час аналізу зв'язку між інваріантом графа і доповненням цього графа:

• Якщо доповнення графа з n вершинами є лінійним лісом, то Шаблон:Nobr;
• Якщо доповнення графа з n вершинами є зовніпланарним графом, то Шаблон:Nobr;
• Якщо доповнення графа з n вершинами є планарним графом, то Шаблон:Nobr.

Мінори графів

Мінором графа G називають граф H, отриманий з G послідовним видаленням вершин, видаленням ребер і стисненням ребер. Інваріант Колена де Вердьєра монотонний відносно операції взяття мінора в тому сенсі, що мінорування графа не може збільшити його інваріанта:

Якщо H є мінором G, то $\mu (H)\le \mu (G)$.

В теоремі Робертсона — Сеймура, для будь-якого k існує H, скінченна множина графів така, що для будь-якого графа з інваріантом не більшим від k графи з H не можуть бути мінорами. В роботі Шаблон:Harvard citation перелічено множини таких недопустимих мінорів для k ≤ 3; для k = 4 множина недопустимих мінорів складається з семи графів сімейства Петерсена за визначенням незачеплено вкладеного графа як графа з μ ≤ 4 і без графів Петерсена як мінорів.

Зв'язок із хроматичним числом

Колен де Вердьєр Шаблон:Harvard citation припустив, що будь-який граф з інваріантом де Вердьера μ можна розфарбувати з використанням не больше ніж μ + 1 кольорів. Наприклад, у лінійних лісів (компоненти яких є двочастковими графами) інваріант дорівнює 1; у зовніпланарних графів інваріант дорівнює 2 і їх можна розфарбувати трьома кольорами; у планарних графів інваріант — 3 і їх можна розфарбувати чотирма кольорами.

Для графів з інваріантом де Вердьєра не більше чотирьох припущення істинне; вони всі є незачеплено вкладаними, і той факт, що вони розфарбовуються п'ятьма кольорами, є наслідком доведення гіпотези Хадвігера для графів без мінорів типу K₆ у роботі Робертсона, Сеймура та Томаса Шаблон:Harvard citation.

Інші властивості

Якщо число перетинів графа дорівнює k, то інваріант де Вердьєра для нього буде не більшим ніж k + 3. Наприклад, графи Куратовського K₅ і K_3,3 можна зобразити з одним перетином, і інваріант для них буде не більшим від чотирьох.

Посилання

• Шаблон:Citation
• Шаблон:Citation.
• Шаблон:Citation
• Шаблон:Citation.
• Шаблон:Citation.