|
ИСТИНА |
Войти в систему Регистрация |
ФНКЦ РР |
||
Характеристический цикл раскраски графастатья
- Авторы: Лавренченко С.А., Магомедов А.М.
- Журнал: Вестник Дагестанского государственного университета. Серия 1: Естественные науки
- Том: 30
- Номер: 6
- Год издания: 2015
- Издательство: Дагестанский государственный университет
- Местоположение издательства: Махачкала
- Первая страница: 68
- Последняя страница: 73
- Аннотация: В статье рассматриваются только конечные неориентированные графы без петель. Реберная раскраска графа называется правильной реберной раскраской, если цвета любых двух смежных ребер различны. Если C - правильная реберная раскраска G и v - вершина из V(G), то S(v, C) обозначает совокупность цветов ребер, инцидентных v. Правильная реберная раскраска C графа G цветами 1, ..., t называется интервальной t-раскраской графа, если использованы все t цветов и для каждой вершины v графа G множество S(v, C) образует интервал целых чисел. Граф G называется интервально раскрашиваемым, если он интервально t-раскрашиваем для некоторого целого положительного t. В 1990 Севастьянов построил двудольный граф с 28 вершинами и максимальной степенью 21, который не имеет интервальной раскраски. В 1991 г. Эрдёш построил двудольный граф с 27 вершинами и максимальной степенью 13, не имеющий интервальной раскраски. В период 1990-2013 гг. контрпример Эрдёша оставался минимальным (в смысле максимальной степени) известным двудольным графом, не имеющим интервальной раскраски. Но в 2013 году Петросян и Хачатрян построили три двудольных графа, которые не имеют интервальной раскраски, содержат 20, 19, 21 вершину и имеют максимальные степени, равные 11, 12 и 13 соответствен-но. Интервальная раскраска графа служит эффективной моделью для изучения задачи составления расписаний без простоев. В данной работе мы приводим новые достаточные условия то-го, что заданный граф не имеет интервальной реберной раскраски.
- Добавил в систему: Лоренс Серж А.