|
Дискретный анализ и исследование операций, 2009, том 16, выпуск 2, страницы 16–20
(Mi da565)
|
|
|
|
Эта публикация цитируется в 18 научных статьях (всего в 18 статьях)
Почти правильные 2-раскраски вершин разреженных графов
О. В. Бородинa, А. О. Ивановаb a Институт математики СО РАН, Новосибирск, Россия
b НИИ математики при Якутском государственном университете, Якутск, Россиия
Аннотация:
Граф $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.
Ключевые слова:
планарный граф, обхват, раскраска, разбиение.
Статья поступила: 09.02.2008
Образец цитирования:
О. В. Бородин, А. О. Иванова, “Почти правильные 2-раскраски вершин разреженных графов”, Дискретн. анализ и исслед. опер., 16:2 (2009), 16–20; J. Appl. Industr. Math., 4:1 (2010), 21–23
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/da565 https://www.mathnet.ru/rus/da/v16/i2/p16
|
Статистика просмотров: |
Страница аннотации: | 624 | PDF полного текста: | 113 | Список литературы: | 58 | Первая страница: | 3 |
|