|
Эта публикация цитируется в 1 научной статье (всего в 1 статье)
К оценке минимального числа цветов в ациклической k-сильной раскраске карт на поверхностях
О. В. Бородинa, А. В. Косточкаa, А. Распоb, Э. Сопенаb a Институт математики им. С. Л. Соболева СО РАН
b Université Bordeaux 1
Аннотация:
Раскраска вершин графа называется ациклической, если концы каждого ребра окрашены в разные цвета и нет двухцветных циклов. Пусть каждая грань ранга не более k, где
k⩾, карта на поверхности S^N заменена на клику с тем же множеством вершин. В [1] доказано, что тогда полученный псевдограф можно ациклически раскрасить в число цветов, линейно зависящее от N и от k. В настоящей заметке эта оценка улучшена до 55(-Nk)^{4/7} цветов при k\ge 1 и -N\ge 5^7k^{4/3}.
Библиография: 8 названий.
Поступило: 29.08.2001
Образец цитирования:
О. В. Бородин, А. В. Косточка, А. Распо, Э. Сопена, “К оценке минимального числа цветов в ациклической k-сильной раскраске карт на поверхностях”, Матем. заметки, 72:1 (2002), 35–37; Math. Notes, 72:1 (2002), 31–42
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/mzm401https://doi.org/10.4213/mzm401 https://www.mathnet.ru/rus/mzm/v72/i1/p35
|
Статистика просмотров: |
Страница аннотации: | 378 | PDF полного текста: | 162 | Список литературы: | 93 | Первая страница: | 3 |
|