Содержание
8 отношения: Кубический граф, Нечётный граф, Рёберная раскраска, Снарк (теория графов), Совершенный граф, Теорема Брукса, Мультиграф Шеннона, Внешнепланарный граф.
Кубический граф
Граф Петерсена является кубическим. Полный двудольный граф K_3,3 является примером бикубического графа Кубический граф — граф, в котором все вершины имеют степень три.
Посмотреть Теорема Визинга и Кубический граф
Нечётный граф
дистанционно-транзитивен обозначение.
Посмотреть Теорема Визинга и Нечётный граф
Рёберная раскраска
графа Дезарга. Рёберная раскраска — назначение «цветов» рёбрам графа таким образом, что никакие два смежных ребра не имеют один и тот же цвет.
Посмотреть Теорема Визинга и Рёберная раскраска
Снарк (теория графов)
Снарк «Цветок» J5 — один из шести снарков с 20 вершинами. Снарк в теории графов — связный кубический граф без мостов c хроматическим индексом 4.
Посмотреть Теорема Визинга и Снарк (теория графов)
Совершенный граф
В теории графов совершенным графом называется граф, в котором хроматическое число любого порождённого подграфа равно размеру максимальной клики этого подграфа.
Посмотреть Теорема Визинга и Совершенный граф
Теорема Брукса
полных графов требуется на единицу больше цветов, чем их максимальная степень. Эти графы и нечётные циклы являются единственными исключениями для теоремы Брукса. Теорема Брукса — утверждение в теории графов, устанавливающее связь между максимальной степенью графа и его хроматическим числом.
Посмотреть Теорема Визинга и Теорема Брукса
Мультиграф Шеннона
В теории графов мультиграфами Шеннона назывется специальный вид треугольных графов, которые используются при исследовании рёберной раскраски.
Посмотреть Теорема Визинга и Мультиграф Шеннона
Внешнепланарный граф
Максимальный внешнепланарный граф и его 3-раскраска. Полный граф K4 является наименьшим планарным графом, не являющимся внешнепланарным. В теории графов outerplanar graph — это граф, допускающий планарную диаграмму, в которой все вершины принадлежат внешней грани.
Посмотреть Теорема Визинга и Внешнепланарный граф