верно ли что хроматический многочлен для n-цепочки...

Вопрос

верно ли что хроматический многочлен для n-цепочки совпадает с хроматическим многочленом для графа-звездочки на n вершинах?

Мысль

Answering chromatic polynomial question

The user is asking if the chromatic polynomial of an n-path graph is the same as that of a star graph on n vertices. It turns out yes! The chromatic polynomial of a path graph $P_n$ is $k(k-1)^{n-1}$ , and since a star graph $S_n$ is also a tree with $n$ vertices and $n-1$ edges, its chromatic polynomial is the same. In general, for any tree with $n$ vertices, the chromatic polynomial is $k(k-1)^{n-1}$ .

Thought for 8 seconds

Ответ

Да, верно.

Более того, не только цепочка $P_n$ и звёздочка $S_n$ имеют одинаковый хроматический многочлен, — любой дерево на $n$ вершинах обладает одним и тем же хроматическим многочленом

P_T(k)=k\,(k-1)^{\,n-1}.

Почему так:

У дерева ровно $n-1$ рёбер и нет циклов.
Уберите любую висячую вершину $v$ (лист). Оставшийся граф $T-v$ всё ещё дерево с $n-1$ вершинами.
Любую правильную $k$ -раскраску $T-v$ можно продолжить на $v$ — у неё есть $k-1$ вариантов цвета (любой, кроме цвета соседней вершины).
Индукция по числу вершин даёт формулу: $P_T(k)=k\,(k-1)^{n-1}.$

Так как и $P_n$ (цепочка) и $S_n$ (звезда) — деревья с одинаковым числом вершин $n$ , их хроматические многочлены совпадают и равны $k\,(k-1)^{\,n-1}$ .

Вопрос

Мысль

Answering chromatic polynomial question

Ответ

Поделиться этим Q&A