Инвариант Колен де Вердьера — характеристика графа , определённая для любого графа G, введённая в 1990 году в процессе исследования кратности второго собственного значения некоторых операторов Шрёдингера.

Определение Пусть  — простой (не содержащий петель и кратных рёбер) ациклический граф. Без потери общности поименуем множество вершин следующим образом: . Тогда  — наибольший коранг любой такой матрицы , что: (M1) для любых , где : , если i и j смежны, и , в противном случае (M2) M имеет ровно одно собственное значение кратности 1; (M3) не существует такой ненулевой матрицы , что , и что всякий раз, когда или .

Классификация известных групп графов С точки зрения инварианта Колен де Вердьера, некоторые хорошо известные семейства графов обладают характерными особенностями: , , при ;. тогда и только тогда, когда G является линейным лесом (лесом, в котором каждый компонент является путём, то есть инцидентность любой вершины не больше 2);В работе этот случай явным образом не рассмотрен, но он явным образом вытекает из результатов анализа графов, не имеющих миноров вида «треугольник» и «клешня». тогда и только тогда, когда G является внешнепланарным графом (все вершины лежат на одной грани); тогда и только тогда, когда G является планарным графом;. тогда и только тогда, когда G является бессвязно встраиваемым, то есть не существует двух циклов в G, для которых при отображении на евклидово пространство (коэффициент зацепления) равен нулю..

Эти же группы графов проявляют свои отличительные черты и при анализе связи между инвариантом графа и дополнением этого графа: Если дополнение графа с n вершинами является линейным лесом, то ;. Если дополнение графа с n вершинами является внешнепланарным графом, то; Если дополнение графа с n вершинами является планарным графом, то .

Миноры графов Минором графа G называют граф H, полученный из G последовательным удалением вершин, удалением рёбер и сжатием рёбер. Инвариант Колена де Вердьера монотонен относительно операции взятия минора в том смысле, что минорирование графа не может увеличить его инвариант: Если H является минором G, то . По теореме Робертсона — Сеймура, для любого k существует H, конечное множество графов такое, что для любого графа с инвариантом не более k графы из H не могут быть минорами. В работе перечисляются множества таких недопустимых миноров для k ≤ 3; для k = 4 множество недопустимых миноров состоит из семи графов Petersen family по определению бессвязно встраиваемого графа как графа с μ ≤ 4 и без графов Петерсена в качестве миноров.

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

Для графов с инвариантом де Вердьера не более четырёх предположение истинно; они все являются бессвязно встраиваемыми, и тот факт, что они раскрашиваются пятью цветами, является следствием доказательства гипотезы Хадвигера для графов без миноров типа K6 в работе .

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

Примечания

Ссылки . Translated by Neil Calkin as . .

. .

Категория:Инварианты графов Категория:Теория миноров графов