Граф Франклина

Шаблон:Граф В теории графов граф Франклина — это 3-регулярный граф с 12 вершинами и 18 рёбрами.

Граф назван именем Шаблон:Не переведено 5, опровергшего гипотезу Хивуда о числе цветов, необходимых для раскраски двумерных поверхностей, разделённых на ячейки при вложении графаШаблон:Sfn. Согласно гипотезе Хивуда максимальное хроматическое число карты на бутылке Клейна должно равняться семи, однако Франклин доказал, что для данного графа шести цветов всегда достаточно. Граф Франклина может быть вложен в бутылку Клейна так, что он образует карту, требующую шесть цветов, что показывает, что в некоторых случаях шести цветов достаточно. Это вложение является Петри двойственным вложения в проективную плоскость (вложение показано ниже).

Граф является гамильтоновым и имеет хроматическое число 2, хроматический индекс 3, радиус 3, диаметр 3 и обхват 4. Он является также вершинно 3-связным и рёберно 3-связным совершенным графом.

Алгебраические свойства

Группа автоморфизмов графа Франклина имеет порядок 48 и изоморфна Z/2Z×S₄, прямому произведению циклической группы Z/2Z и симметрической группы S₄. Группа действует транзитивно на вершинах графа.

Характеристический многочлен графа Франклина равен

$(x-3)(x-1{)}^3(x+1{)}^3(x+3)(x^2-3{)}^2.$

Галерея

• 
  Хроматическое число графа Франклина равно 2.
• 
  Хроматический индекс графа Франклина равен 3.
• 
  Альтернативный рисунок графа Франклина.
• 
  Граф Франклина, вложенный в проективную плоскость как усечённый Шаблон:Не переведено 5.

Литература

• Шаблон:Статья