RUS  ENG
Полная версия
ЖУРНАЛЫ // Математические заметки // Архив

Матем. заметки, 2002, том 72, выпуск 1, страницы 35–37 (Mi mzm401)

Эта публикация цитируется в 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 названий.

УДК: 519.174

Поступило: 29.08.2001

DOI: 10.4213/mzm401


 Англоязычная версия: Mathematical Notes, 2002, 72:1, 31–42

Реферативные базы данных:


© МИАН, 2024