RUS  ENG
Полная версия
ЖУРНАЛЫ // Дискретный анализ и исследование операций // Архив

Дискретн. анализ и исслед. опер., сер. 1, 2006, том 13, выпуск 1, страницы 16–32 (Mi da21)

Эта публикация цитируется в 25 статьях

Ориентированная 5-раскраска вершин в разреженных графах

О. В. Бородинa, А. О. Ивановаb, А. В. Косточкаac

a Институт математики им. С. Л. Соболева СО РАН
b Якутский государственный университет им. М. К. Аммосова
c University of Illinois at Urbana-Champaign

Аннотация: Ориентированная $k$-раскраска вершин ориентированного графа $H$ есть ориентированный гомоморфизм из $H$ в некоторый $k$-вершинный турнир. Доказано, что любая ориентация графа с обхватом не менее 5 и максимальной средней степенью его подграфов менее 12/5 имеет ориентированную 5-раскраску. Как следствие, любая ориентация плоского или проективно плоского графа с обхватом не менее 12 имеет ориентированную 5-раскраску.

УДК: 517.71

Статья поступила: 27.09.2005


 Англоязычная версия: Journal of Applied and Industrial Mathematics, 2007, 1:1, 9–17

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


© МИАН, 2024