задача определения хроматического полинома графа

Question

для теории графов домашних заданий меня просят определить хроматический полином следующего графа

Для теоремы о разложении хроматических полиномов . если G = (V, E), связный граф и e принадлежат E

P (G, λ) = P (Ge, λ) -P(Ge', λ)

, где Ge обозначает подграф, полученный удалением ребра e из G (Ge = G-e), а Ge '- подграф, полученный путем идентификации вершин {a, b} = e

При вычислении хроматических полиномов я должен поставить квадратные скобки вокруг графа, чтобы указать его хроматический полином. удаляет ребро любого исходного графа для вычисления хроматического полинома методом разложения.

 P (G, λ) = P (Ge, λ)-P (Ge', λ) = λ (λ-1)^4 - [λ(λ-1)*(λ^2 - 3λ + 3)]

Но ответ от ключа ответа и учителя:

P (G, λ) = λ (λ-1)(λ-2)(λ^2-2λ-2)

Я оперировал полиномом, но не могу найти решение, которое спрашиваю ... что я делаю не так?

Answer 1

Ваш ответ правильный, как и у учителя - они равны. [Кстати, хорошая картинка и объяснение.]

Нечетный цикл не может иметь 2-окраски, следовательно, 5-цикл может не имеют 2-окраски, поэтому его хроматический полином f (x), должен иметь x * [x - 1] * [x - 2]

как делитель. Если вы комбинируете выражение для f (x) и разделить

x * [x - 1]

тогда вы обнаружите, что то, что осталось, делится на [x - 2], и фактор то, что написал ваш учитель. Джонатан Кинг

Answer 2

math.stackexchange.com сказал мне, как решить мою проблему. Вот решение:

https://math.stackexchange.com/questions/33946/problem-to-determine-the-chromatic-polynomial-of-a-graph

Answer 3

В книге, которой я следую (Теория графов с приложениями - Део Прентис Холл), все сделано по-другому. Вместо исключения ребра они соединяют две несмежные вершины.

Используя эту технику, я получаю

P (G, λ) = 2λ(λ-1)^2(λ-2) + 2λ(λ-1)(λ-2)(λ-3) + λ(λ-1)(λ-2)(λ-3)(λ-4), что также не равно ни одному из ваших результатов.