Хроматический многочлен

Cтраница 1

Граф пересечений.| Две операции над графом. [1]

Хроматические многочлены замечательны тем, что они, как нетрудно видеть, удовлетворяют следующему условию. [2]

Хроматические многочлены были введены нами с целью подсчета числа п-раскрасок графов. Было бы уместно привести здесь дальнейшие результаты о раскрасках. Но, к сожалению, способы получения этих результатов немногочисленны и, обычно, весьма сложны ( за редким исключением, когда они тривиальны), особенно если, как в нашем изложении, не используется свойство планарности. Приведем два примера, один из которых тривиален, а другой, напротив, достаточно сложен. [3]

Хроматический многочлен графа введен Биркгофом и Льюисом [1], когда они предпринимали попытки решить гипотезу четырех красок. Раскраской графа G t цветами называется раскраска графа 6, использующая t или меньше цветов. Две раскраски графа G t цветами будем считать различными, если по крайней мере одной помеченной вершине приписываются различные цвета. [4]

Очень часто хроматические многочлены возникают при рассмотрении триангуляции сферы. [5]

Как и хроматический многочлен, потоковый многочлен графа С - это графовая функция, являющаяся многочленом от переменной Я с целыми коэффициентами. [6]

Рид [4] предположил, что абсолютные значения коэффициентов любого хроматического многочлена сначала строго возрастают, затем строго убывают и, наконец, не меняются. [7]

По очевидным соображениям МС ( А) называют хроматическим многочленом графа G. Если мы не имеем простого способа вычисления значений ц, то нахождение многочлена Мс ( А) становится трудной задачей. Хроматические многочлены были введены Биркгофом и Люисом [2] при исследовании проблемы четырех красок. Хорошим упражнением является повторение некоторых доказательств Рида с использованием свойств ц-функции. [8]

Пусть хМх ( б, А) - значение хроматического многочлена графа G, вычисленное для АеС, где С - множество комплексных чисел. Если А - целое неотрицательное число, то х ( А) имеет следующую нетрадиционную интерпретацию. [9]

Остается нерешенной задача описания графов, имеющих один и тот же хроматический многочлен. Более общая нерешенная задача состоит в нахождении необходимого и достаточного условия для того, чтобы многочлен был хроматическим. Например, многочлен t - 3 / 3 З 2 обладает всеми известными свойствами хроматического многочлена, но не является хроматическим. [10]

Обычно на каждом шаге рисуют сам граф, а не выписывают его хроматический многочлен. [11]

В заключение этой главы скажем несколько слов о том, как связаны хроматические многочлены и раскрашивае-мость с задачей составления расписания. [12]

Ясно, что каждые два изоморфных графа имеют один и тот же хроматический многочлен. Однако часто несколько неизоморфных графов также имеют один и тот же хроматический многочлен. [13]

Соотношение ( 1) служит обоснованием следующего утверждения, приведенного в [4]: аналогом хроматического многочлена X для частично упорядоченного множества является строгий порядковый многочлен И. [14]

Используя в качестве основного средства обращение Мебиуса, Крапо и Рота [3] показали, что проблема четырех красок и изучение хроматических многочленов являются частными случаями более общей задачи, а именно критической проблемы для комбинаторных геометрий. [15]

Страницы: 1 2 3