|
Эта публикация цитируется в 1 научной статье (всего в 1 статье)
К оценке минимального числа цветов в ациклической $k$-сильной раскраске карт на поверхностях
О. В. Бородинa, А. В. Косточкаa, А. Распоb, Э. Сопенаb a Институт математики им. С. Л. Соболева СО РАН
b Université Bordeaux 1
Аннотация:
Раскраска вершин графа называется ациклической, если концы каждого ребра окрашены в разные цвета и нет двухцветных циклов. Пусть каждая грань ранга не более $k$, где
$k\ge 4$, карта на поверхности $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
|
Статистика просмотров: |
Страница аннотации: | 369 | PDF полного текста: | 153 | Список литературы: | 83 | Первая страница: | 3 |
|