Гомоморфизмы

В этом разделе мы для удобства будем рассматривать только связные графы . Элементарным гомоморфизмом графаG называется отождествление двух его несмежных вершин. Гомоморфизмграфа G-это последовательность его элементарных гомоморфизмов.

Пусть G'— граф, который получается из графа G при гомоморфизме . Тогдаможно рассматривать как функцию, отображающую V на V' такую, что если u и v смежны в G, тоu иv смежны в G'. Заметим, что каждое ребро графа G' должно получаться из некоторого ребра графа G, т. е. еслиu' и v' смежны в G', то в G найдутся такие вершины u и v, чтоu=u' иv = v'.

Будем говорить, что

- гомоморфизмграфа G на граф G', а граф G'-гомоморфный образграфа G, и писать G'=G. Так, в частности, каждый изоморфизм является гомоморфизмом. Простая цепь Р4 имеет четыре гомоморфных образа, которые изображены на рисунке.

Гомоморфизм графа G называетсяполным порядка n, если

G =Kn. Отметим, что каждый гомоморфизмграфа G на полный граф

Кnсоответствует n-раскраске графа G, поскольку вершины графа Кnможно рассматривать как цвета и по определению гомоморфизма ни одна пара вершин графа G с одинаковым цветом не смежна. Любая раскраска, определенная полным гомоморфизмом, обладает тем свойством, что для любых двух цветов в графе G найдутся смежные вершины г и v, окрашенные в эти цвета. В данном случае мы получаемполную раскраску. На рисунке показан граф с полными раскрасками порядков 3 и 4; Очевидно, что наименьший порядок всех полных гомоморфизмов графа G должен быть равным хr(G).

Теорема (Харари, Хедетниеми, Принс ) обобщает более ранний результат Хайоша, который будет приведен как ее следствие.

Теорема.Для любого графа G и любого его элементарного гомоморфизма xr(G)<xr(G)<l + xr(G).

Доказательство. Пусть- элементарный гомоморфизм графа G, отождествляющий несмежные вершиныuи v. Тогда любая раскраска графаG порождает раскраску графа G, еслиuи v окрашены в один и тот же цвет; поэтому xr(G)<xr(G). С другой стороны, раскраска графаG получается из раскраски графа G, когда новой вершине приписывается цвет, отличный от всех цветов, используемых в раскраске G, так что хr(G)<1 + хr(G)

Следствие(а).Для любого гомоморфизма  графа G

xr(G)<xr(G).

Естественно теперь рассмотреть наибольший порядок всех полных гомоморфизмов графа G. Этот инвариант называется ахроматическим числоми обозначается(G). Поскольку G можно раскрасить р цветами, очевидно, что xr(G)<(G)<p. Ни одно из этих неравенств не дает хорошей оценки для;.

Теорема.Для любого графа G и любого его элементарного гомоморфизма

 (G)—2< (G)<  (G).

Пример на рисунке показывает, что нижняя оценка достигается и, следовательно, она неулучшаема. Легко проверить, что (G)=5, в то время как(G)=3.

Теорема , названная в работе Харари, Хедетниеми и Принса теоремой об интерполяции гомоморфизмов, сильно зависит от оценок.

Теорема.Для любого графа G и любого целого числа n, заключенного между xr(G) u (G), существует полный гомоморфизм (и, следовательно, полная раскраска) порядка n.

Теорема.Для любого графа G

+хr<p+1.

Следствие(а).Для любого графа G

<р—0+1.