Реберно 4-критический граф Кёстера порядка 28

Аннотация

Граф Кестера есть простой 4-регулярный плоский граф, образованный суперпозицией множества S окружностей на плоскости, никакие две из которых не касаются друг друга, и никакие три окружности не имеют общей точки. Точки пересечения и дуги окружностей соответствуют вершинам и ребрам графа соответственно. В работе построен 4-хроматический реберно критический граф Кёстера порядка 28, порожденный пересечением шести окружностей. Это улучшает верхнюю границу для наименьшего порядка таких графов. Предыдущая верхняя граница была установлена Герхардом Кёстером в 1984 году построением графа на 40 вершинах.