Тороїдальний граф

Тороїдальний граф — це граф, який можна вкласти на тор; іншими словами, це — граф, вершини якого можна розмістити на торі так, що ребра не схрещуватимуться.

Кубічний граф з 14 вершинами, вкладений в тор

Приклади

Будь-який граф, який можна вкласти у площину, також можна вкласти у тор. Тороїдальний будь-який граф із числом схрещень 1, наприклад: граф Хівуда, повний граф ${\displaystyle K_{7}}$ (і як наслідок, ${\displaystyle K_{5}}$ та ${\displaystyle K_{6}}$), граф Петерсена, один зі снарків Блануші^[1] та всі драбини Мебіуса. Деякі графи з великим числом схрещень також є тороїдальними, наприклад, граф Мебіуса — Кантора, який має число схрещень 4^[2].

Властивості

Хроматичне число будь-якого тороїдального графа не перевищує 7^[3]; прикладом тороїдального графа з хроматичним числом 7 є повний граф ${\displaystyle K_{7}}$^[4]. Хроматичне число будь-якого тороїдального графа без трикутників не перевищує 4^[5].

Аналогічно теоремі Фарі, будь-який тороїдальний граф можна побудувати з ребрами у вигляді відрізків у прямокутнику з періодичними межами (тобто протилежні границі квадрата ототожнюються)^[6]. Крім того, у цьому випадку може бути застосована теорема Татта^[7].

Тороїдальні графи також допускають книжкове вкладення з максимум 7 листами^[8].

Див. також

• Багатогранник Часара^[en]
• Планарний граф
• Топологічна теорія графів