"Записки научных семинаров ПОМИ"

Том 406, стр. 12-30

С.-Петербургское отделение Математического института им. В. А. Стеклова РАН Фонтанка 27, 191023 Санкт-Петербург, Россия

dvk0@yandex.ru

Аннотация: Пусть $G$ -- двудольный граф без петель и кратных рёбер на $v\ge 4$ вершинах, который можно изобразить на плоскости так, чтобы каждое ребро пересекало не более, чем одно другое. В работе доказывается, что при чётном~$v\ne 6$ в таком графе не более чем $3v-8$ рёбер, а при нечетном~$v$ и~$v=6$ -- не более чем $3v-9$ рёбер. Для всех~$v\ge 4$ построены примеры графов, для которых эти оценки достигаются. В конце работы мы обсудим вопрос об изображении на плоскости полных двудольных графов с условием, что каждое ребро пересекает не более, чем одно другое. Библ. -- 6 назв.
Ключевые слова:планарные графы, число пересечений, двудольные графы [topological graphs, planar graphs, bipartite graphs]