Explicit formulas for chromatic polynomials of some series-parallel graphs

Основная цель работы — представить явные формулы для вычисления хроматических многочленов некоторых параллельно-последовательных графов (sp-графов). Граф колье, рассматриваемый в данной работе, это простейший нетривиальный sp-граф. Мы дадим явную формулу для вычисления графа-колье общего вида. Кроме того, будут даны явные формулы для вычисления хроматических многочленов графов кольцо из колье и колье из колье произвольного вида.
Хроматические многочлены графов колье и кольцо из колье изначально получены нами при помощи перехода к двойственному графу и дальнейшему использованию потокового многочлена. Кроме того, мы использовали технику конечного преобразования Фурье.
Более универсальным способом подсчета хроматических многочленов является использование статистической суммы модели Поттса. Идея используемых здесь тождеств параллельного и последовательного сокращения была предложена Аланом Сокалом. Мы разовьем эту идею и введем преобразование сокращения графа колье. Использование этого преобразования позволяет упростить вычисление хроматических многочленов графов колье, кольцо из колье и вычислить хроматический многочлен графа колье из колье.