Дискретный анализ и исследование операций
RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB  
Общая информация
Последний выпуск
Архив
Импакт-фактор
Правила для авторов

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Дискретн. анализ и исслед. опер.:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Дискретный анализ и исследование операций, 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$$\mathrm{mad}(G_n)=(18n-2)/(7n-1)$, не являющийся $(2,1)$-раскрашиваемым. Библиогр. 5.
Ключевые слова: планарный граф, обхват, раскраска, разбиение.
Статья поступила: 09.02.2008
Англоязычная версия:
Journal of Applied and Industrial Mathematics, 2010, Volume 4, Issue 1, Pages 21–23
DOI: https://doi.org/10.1134/S1990478910010047
Реферативные базы данных:
УДК: 519.172.2
Образец цитирования: О. В. Бородин, А. О. Иванова, “Почти правильные 2-раскраски вершин разреженных графов”, Дискретн. анализ и исслед. опер., 16:2 (2009), 16–20; J. Appl. Industr. Math., 4:1 (2010), 21–23
Цитирование в формате AMSBIB
\RBibitem{BorIva09}
\by О.~В.~Бородин, А.~О.~Иванова
\paper Почти правильные 2-раскраски вершин разреженных графов
\jour Дискретн. анализ и исслед. опер.
\yr 2009
\vol 16
\issue 2
\pages 16--20
\mathnet{http://mi.mathnet.ru/da565}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=2574306}
\zmath{https://zbmath.org/?q=an:1249.05110}
\transl
\jour J. Appl. Industr. Math.
\yr 2010
\vol 4
\issue 1
\pages 21--23
\crossref{https://doi.org/10.1134/S1990478910010047}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-77949893758}
Образцы ссылок на эту страницу:
  • https://www.mathnet.ru/rus/da565
  • https://www.mathnet.ru/rus/da/v16/i2/p16
  • Эта публикация цитируется в следующих 18 статьяx:
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Дискретный анализ и исследование операций
    Статистика просмотров:
    Страница аннотации:624
    PDF полного текста:113
    Список литературы:58
    Первая страница:3
     
      Обратная связь:
     Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2024