Семейства плоских 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-связных графов) и сформулированы нерешенные проблемы в этой области.