Том 13, серия 1, номер 1, 2006 г., Стр. 16-32
УДК 517.71
О. В. Бородин, А. О. Иванова, А. В. Косточка
Ориентированная 5-раскраска вершин в разреженных графах
Аннотация:
Ориентированная$k$ -раскраска вершин ориентированного графа$H$ есть ориентированный гомоморфизм из$H$ в некоторый$k$ -вершинный турнир. Доказано, что любая ориентация графа с обхватом не менее 5 и максимальной средней степенью его подграфов менее 12/5 имеет ориентированную 5-раскраску. Как следствие, любая ориентация плоского или проективно плоского графа с обхватом не менее 12 имеет ориентированную 5-раскраску.
Бородин О. В. 1
Иванова А. О. 2
Косточка А. В. 1,3
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
2. Якутский государственный университет им. М. К. Аммосова,
Институт математики и информатики,
ул. Кулаковского, 48, 677000 Якутск, Россия
3. Университет штата Иллинойс, кафедра математики,
Урбана, IL-61801, США
е-mail: brdnoleg@math.nsc.ru, shmgnanna@mail.ru, sasha@math.nsc.ru, kostochk@math.uiuc.edu
Статья поступила 27 сентября 2005 г.
