Инвариант Колен де Вердьера

Инвариант Колен де Вердьера — характеристика графа $\mathrm{\mu <!--\; \mu \; -->}(G)$$\mu (G)$, определённая для любого графа G, введённая Ивом Колен де Вердьером (фр.) в 1990 году в процессе исследования кратности второго собственного значения некоторых операторов Шрёдингера.

ОпределениеПравить

Пусть $G=(V,E)$$G=(V,E)$  — простой (не содержащий петель и кратных рёбер) ациклический граф. Без потери общности поименуем множество вершин следующим образом: $V=\{1,\dots <!--\; \dots \; -->,n\}$$V=\{1,\dots ,n\}$ . Тогда $\mathrm{\mu <!--\; \mu \; -->}(G)$$\mu (G)$  — наибольший коранг любой такой матрицы $M=(M_{i,j})\in <!--\; \in \; -->{\mathbb{R}}^{(n)}$$M=(M_{i,j})\in \mathbb {R} ^{(n)}$ , что:

• (M1) для любых $i,j$$i,j$ , где $i\ne <!--\; \ne \; -->j$$i\neq j$ : $M_{i,j}<0$ , если i и j смежны, и $M_{i,j}=0$$M_{i,j}=0$  , в противном случае
• (M2) M имеет ровно одно собственное значение кратности 1;
• (M3) не существует такой ненулевой матрицы $X=(X_{i,j})\in <!--\; \in \; -->{\mathbb{R}}^{(n)}$$X=(X_{i,j})\in \mathbb {R} ^{(n)}$ , что $MX=0$$MX=0$ , и что $X_{i,j}=0$$X_{i,j}=0$  всякий раз, когда $i=j$$i=j$  или $M_{i,j}\ne <!--\; \ne \; -->0$$M_{i,j}\neq 0$ .

Классификация известных групп графовПравить

С точки зрения инварианта Колен де Вердьера, некоторые хорошо известные семейства графов обладают характерными особенностями:

• $\mathrm{\mu <!--\; \mu \; -->}(K_1)=0$$\mu (K_{1})=0$ , $\mathrm{\mu <!--\; \mu \; -->}(K_n)=n-<!--\; -\; -->1$$\mu (K_{n})=n-1$ , $\mathrm{\mu <!--\; \mu \; -->}(\stackrel{¯<!--\; ¯\; -->}{K_n})=1$$\mu ({\overline {K_{n}}})=1$  при $n>1$$n>1$ ;
• μ ≤ 1 тогда и только тогда, когда G является линейным лесом (лесом, в котором каждый компонент является путём, то есть инцидентность любой вершины не больше 2);
• μ ≤ 2 тогда и только тогда, когда G является внешнепланарным графом (все вершины лежат на одной грани);
• μ ≤ 3 тогда и только тогда, когда G является планарным графом;
• μ ≤ 4 тогда и только тогда, когда G является бессвязно встраиваемым, то есть не существует двух циклов в G, для которых при отображении на евклидово пространство (коэффициент зацепления) равен нулю.

Эти же группы графов проявляют свои отличительные черты и при анализе связи между инвариантом графа и дополнением этого графа:

• Если дополнение графа с n вершинами является линейным лесом, то μ ≥ n − 3;
• Если дополнение графа с n вершинами является внешнепланарным графом, тоμ ≥ n − 4;
• Если дополнение графа с n вершинами является планарным графом, то μ ≥ n − 5.

Миноры графовПравить

Минором графа G называют граф H, полученный из G последовательным удалением вершин, удалением рёбер и сжатием рёбер. Инвариант Колена де Вердьера монотонен относительно операции взятия минора в том смысле, что минорирование графа не может увеличить его инвариант:

Если H является минором G, то $\mathrm{\mu <!--\; \mu \; -->}(H)\le <!--\; \le \; -->\mathrm{\mu <!--\; \mu \; -->}(G)$$\mu (H)\leq \mu (G)$ .

По теореме Робертсона — Сеймура, для любого k существует H, конечное множество графов такое, что для любого графа с инвариантом не более k графы из H не могут быть минорами. В работе (Colin de Verdière 1990) перечисляются множества таких недопустимых миноров для k ≤ 3; для k = 4 множество недопустимых миноров состоит из семи графов Petersen family (англ.) по определению бессвязно встраиваемого графа как графа с μ ≤ 4 и без графов Петерсена в качестве миноров.

Связь с хроматическим числомПравить

(Colin de Verdière 1990) предположил, что любой граф с инвариантом де Вердьера μ может быть раскрашен с использованием не более чем μ + 1 цветов. Например, у линейных лесов (компоненты которых являются двудольными графами) инвариант равняется 1; у внешнепланарных графов инвариант равняется 2, и они могут быть раскрашены тремя цветами; у планарных графов инвариант — 3, и они могут быть раскрашены четырьмя цветами.

Для графов с инвариантом де Вердьера не более четырёх предположение истинно; они все являются бессвязно встраиваемыми, и тот факт, что они раскрашиваются пятью цветами, является следствием доказательства гипотезы Хадвигера для графов без миноров типа K₆ в работе (Robertson, Seymour & Thomas 1993).

Другие свойстваПравить

Если число пересечений графа равно k, то инвариант де Вердьера для него будет не более k + 3. Например, графы Куратовского K₅ и K_3,3 могут быть изображены с одним пересечением, и инвариант для них будет не более четырёх.

СсылкиПравить

• Colin de Verdière, Y. (1990), Sur un nouvel invariant des graphes et un critère de planarité, Journal of Combinatorial Theory, Series B Т. 50 (1): 11–21, DOI 10.1016/0095-8956(90)90093-F . Translated by Neil Calkin as Colin de Verdière, Y. (1993), On a new graph invariant and a criterion for planarity, in Robertson, Neil & Seymour, Paul, Graph Structure Theory: Proc. AMS–IMS–SIAM Joint Summer Research Conference on Graph Minors, vol. 147, Contemporary Mathematics, American Mathematical Society, с. 137–147 .
• van der Holst, Hein; Lovász, László & Schrijver, Alexander (1999), The Colin de Verdière graph parameter, Graph Theory and Combinatorial Biology (Balatonlelle, 1996), vol. 7, Bolyai Soc. Math. Stud., Budapest: János Bolyai Math. Soc., с. 29–85, <http://www.cs.elte.hu/~lovasz/colinsurv.ps> .
• Kotlov, Andrew; Lovász, László & Vempala, Santosh (1997), The Colin de Verdiere number and sphere representations of a graph, Combinatorica Т. 17 (4): 483–521, doi:10.1007/BF01195002, <http://oldwww.cs.elte.hu/~lovasz/sphere.ps> 
• Lovász, László & Schrijver, Alexander (1998), A Borsuk theorem for antipodal links and a spectral characterization of linklessly embeddable graphs, Proceedings of the American Mathematical Society Т. 126 (5): 1275–1285, DOI 10.1090/S0002-9939-98-04244-0 .
• Robertson, Neil; Seymour, Paul & Thomas, Robin (1993), Hadwiger's conjecture for K₆-free graphs, Combinatorica Т. 13: 279–361, doi:10.1007/BF01202354, <http://www.math.gatech.edu/~thomas/PAP/hadwiger.pdf> .