Введение
Инвариант Колина де Вердьера — это параметр графа для любого графа G, введенный Ивом Колином де Вердьером в 1990 году. Он был мотивирован изучением максимальной кратности второго собственного значения определенных операторов Шрёдингера. μ ≤ 2 тогда и только тогда, когда G является внешнепланарным; μ ≤ 4 тогда и только тогда, когда G может быть вложен в R3 без связей. Те же самые семейства графов также возникают в связи между инвариантом Колина де Вердьера графа и структурой его дополнения: если дополнение графа с n вершинами является линейным лесом, то μ ≥ n − 3; если дополнение графа с n вершинами является внешнепланарным, то μ ≥ n − 4.
Colin de Verdière's invariant is a graph parameter for any graph G, introduced by Yves Colin de Verdière in 1990. It was motivated by the study of the maximum multiplicity of the second eigenvalue of certain Schrödinger operators. μ ≤ 2 if and only if G is outerplanar;
μ ≤ 4 if and only if G is linklessly embeddable in R3. These same families of graphs also show up in connections between the Colin de Verdière invariant of a graph and the structure of its complement:
If the complement of an n vertex graph is a linear forest, then μ ≥ n − 3;
If the complement of an n vertex graph is outerplanar, then μ ≥ n − 4;
Хроматическое число
Предполагается, что любой граф с инвариантом Колина де Вердьера μ может быть раскрашен не более чем в μ + 1 цветов. Например, линейные леса имеют инвариант 1 и могут быть раскрашены в 2 цвета; внешнепланарные графы имеют инвариант 2 и могут быть раскрашены в 3 цвета; планарные графы имеют инвариант 3 и (по теореме о четырех цветах) могут быть раскрашены в 4 цвета. Для графов с инвариантом Колина де Вердьера, не превосходящим четыре, предположение остаётся верным; это графы, допускающие линковую встраиваемость, и тот факт, что их хроматическое число не превосходит пяти, является следствием доказательства гипотезы Хадвигера для графов, не содержащих K6 в качестве минора.
Другие свойства
Если граф имеет число пересечений cr, то его инвариант Колина де Вердьера не превосходит 4cr. Например, два графа Куратовского K₃,₃ и K₅ могут быть изображены с единственным пересечением, и их инвариант Колина де Вердьера не превосходит четырех.
Влияние
Инвариант Колина де Вердьера определяется посредством класса матриц, соответствующих графу, а не только одной матрицей. Аналогичным образом могут быть определены и исследованы другие параметры графа, такие как минимальный ранг, минимальный полуположительный ранг и минимальный косой ранг.