В математической области теории графов граф Франклина представляет собой 3- регулярный граф с 12 вершинами и 18 ребрами.
Граф Франклина назван в честь Филиппа Франклина , который опроверг гипотезу Хивуда о количестве цветов, необходимых при разбиении двумерной поверхности на ячейки с помощью вложения графа . [1] Гипотеза Хивуда подразумевала, что максимальное хроматическое число карты на бутылке Клейна должно быть равно семи, но Франклин доказал, что в этом случае шести цветов всегда достаточно. (Бутылка Клейна — единственная поверхность, для которой гипотеза Хивуда неверна.) Граф Франклина можно вложить в бутылку Клейна так, чтобы он образовал карту, требующую шести цветов, что показывает, что в этом случае иногда необходимо шесть цветов. Это вложение является двойственным по Петри его вложению в проективную плоскость, показанную ниже.
Он является гамильтоновым и имеет хроматическое число 2, хроматический индекс 3, радиус 3, диаметр 3 и обхват 4. Он также является 3- вершинно-связным и 3- рёберно-связным совершенным графом .
Группа автоморфизмов графа Франклина имеет порядок 48 и изоморфна Z / 2 Z × S 4 , прямому произведению циклической группы Z /2 Z и симметрической группы S 4 . Она действует транзитивно на вершинах графа, делая его вершинно-транзитивным .
Характеристический многочлен графа Франклина равен
