Том 16, номер 2, 2009 г., Стр. 16-20
УДК 519.172.2
О. В. Бородин, А. О. Иванова
Почти правильные 2-раскраски вершин разреженных графов
Аннотация:
Граф$G$ называется$(2,1)$ -раскрашиваемым, если множество его вершин можно разбить на два подмножества$V_1$ и$V_2$ так, что в$G[V_1]$ любая компонента содержит не более двух вершин, а в$G[V_2]$ нет рёбер. Доказано, что любой граф$G$ с максимальной средней степенью$\mathrm{mad}(G)$ меньшей 7/3 является$(2,1)$ -раскрашиваемым. Отсюда следует, что каждый плоский граф с обхватом не менее 14 является$(2,1)$ -раскрашиваемым. Построен плоский граф$G_n$ c$\mathrm{mad}(G_n)=(18n-2)/(7n-1)$ , не являющийся$(2,1)$ -раскрашиваемым.
Библиогр. 5.
Ключевые слова: планарный граф, обхват, раскраска, разбиение.
Бородин Олег Вениаминович 1
Иванова Анна Олеговна 2
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
2.
НИИ математики при Якутском государственном университете,
677891 Якутск, Россия
е-mail: brdnoleg@math.nsc.ru, shmgnanna@mail.ru
Статья поступила 9 февраля 2008 г.
