Содержание
6 отношения: Однозначно раскрашиваемый граф, Рёберная раскраска, Теорема Брукса, Теорема Визинга, Визинг, Вадим Георгиевич, 1-планарный граф.
Однозначно раскрашиваемый граф
Однозначно раскрашиваемый граф — это k-цветный граф, допускающий только одну (правильную) ''k''-раскраску (с точностью до перестановки цветов).
Посмотреть Тотальная раскраска и Однозначно раскрашиваемый граф
Рёберная раскраска
графа Дезарга. Рёберная раскраска — назначение «цветов» рёбрам графа таким образом, что никакие два смежных ребра не имеют один и тот же цвет.
Посмотреть Тотальная раскраска и Рёберная раскраска
Теорема Брукса
полных графов требуется на единицу больше цветов, чем их максимальная степень. Эти графы и нечётные циклы являются единственными исключениями для теоремы Брукса. Теорема Брукса — утверждение в теории графов, устанавливающее связь между максимальной степенью графа и его хроматическим числом.
Посмотреть Тотальная раскраска и Теорема Брукса
Теорема Визинга
Теорема Визинга — утверждение теории графов, согласно которому рёбра любого неориентированного графа могут быть раскрашены в число цветов, максимум на единицу большее максимальной степени вершин \delta графа.
Посмотреть Тотальная раскраска и Теорема Визинга
Визинг, Вадим Георгиевич
Вадим Георгиевич Визинг (25 марта 1937, Киев — 23 августа 2017, Одесса) — советский и украинский, известный благодаря исследованиям в теории графов, прежде всего — теореме Визинга.
Посмотреть Тотальная раскраска и Визинг, Вадим Георгиевич
1-планарный граф
графа Хивуда — шесть рёбер имеют единичные пересечения, а остальные 15 рёбер не пересекаются. В топологической теории графов 1-планарный граф — это граф, который может быть нарисован в евклидовой плоскости таким образом, что каждое ребро имеет максимум одно пересечение с единственным другим ребром.
Посмотреть Тотальная раскраска и 1-планарный граф