Том 11, серия 2, номер 1, 2004 г., Стр. 80-116

УДК 519.17
Л. С. Мельников
Семейства плоских 4-однородных 4-критических графов

Аннотация:
В 1985 году Г. Кёстер построил пример 40-вершинного плоского 4-однородного 4-критического графа $G^*$, опровергнув гипотезу Т. Галлаи и Г. А. Дирака о справедливости верхней оценки $e\leqslant 2v-2$ числа ребер $e$ через число вершин $v$ и гипотезу Г. Грёцша о 3-хроматичности. Позднее в 1990–91 годах Г. Кёстер построил бесконечные семейства 3- и 4-связных графов, начиная с $G^*$ и с шагом в 9 и 15 вершин соответственно. В настоящей статье построен пример 31-вершинного плоского 4-однородного 4-критического графа $G^0_3$. На его основе построены бесконечные семейства 3- и 4-связных плоских 4-однородных 4-критических графов, начиная с $G^0_3$ и с шагом в 3 вершины в обоих случаях. Дан обзор результатов по $k$-критическим графам и плоским 4-критическим графам, показывающих важность рассматриваемых свойств графов. Приведены некоторые следствия (в частности, о максимальном числе треугольников, максимальной степени грани). Усилена нижняя оценка предела средней степени плоских 4-критических 3-связных графов) и сформулированы нерешенные проблемы в этой области.

Мельников Л. С. ¹
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
е-mail: omeln@math.nsc.ru

Статья поступила 24 октября 2003 г.