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

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

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



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






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


Сиб. матем. журн., 2011, том 52, номер 5, страницы 1004–1010 (Mi smj2253)  

Эта публикация цитируется в 15 научных статьях (всего в 15 статьях)

Вершинные разбиения разреженных графов на независимое множество и подграф максимальной степени не более $1$

О. В. Бородинab, А. В. Косточкаac

a Институт математики им. С. Л. Соболева СО РАН, Новосибирск
b Новосибирский гос. университет, Новосибирск
c Университет штата Иллинойс, кафедра математики, Урбана, IL, США

Аннотация: Граф $G$ называется $(1,0)$-раскрашиваемым, если множество его вершин можно разбить на подмножества $V_1$ и $V_0$ так, чтобы в подграфе $G[V_1]$ каждая вершина имела степень не больше $1$, а $G[V_0]$ не содержал ребер. Доказано, что всякий граф c максимальной средней степенью не более $\frac{12}5$ является $(1,0)$-раскрашиваемым. В частности, отсюда следует $(1,0)$-раскрашиваемость любого плоского графа обхвата не менее $12$. С другой стороны, построены графы с максимальной средней степенью, сколь угодно близкой (сверху) к $\frac{12}5$, которые не имеют $(1,0)$-раскраски.
Фактически в работе получен более сильный результат: найдено неулучшаемое достаточное условие $(1,0)$-раскрашиваемости графа $G$ в терминах минимума, $Ms(G)$, разности $6|V(A)|-5|E(A)|$ по всем подграфам $A$ графа $G$. А именно, доказано, что всякий граф $G$ с $Ms(G)\ge-2$ является $(1,0)$-раскрашиваемым, и построена бесконечная серия $(1,0)$-нераскрашиваемых графов $G$ с $Ms(G)=-3$.

Ключевые слова: плоские графы, раскраска, обхват.

Полный текст: PDF файл (290 kB)
Список литературы: PDF файл   HTML файл

Англоязычная версия:
Siberian Mathematical Journal, 2011, 52:5, 796–801

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

Тип публикации: Статья
УДК: 519.17
Статья поступила: 15.07.2010

Образец цитирования: О. В. Бородин, А. В. Косточка, “Вершинные разбиения разреженных графов на независимое множество и подграф максимальной степени не более $1$”, Сиб. матем. журн., 52:5 (2011), 1004–1010; Siberian Math. J., 52:5 (2011), 796–801

Цитирование в формате AMSBIB
\RBibitem{BorKos11}
\by О.~В.~Бородин, А.~В.~Косточка
\paper Вершинные разбиения разреженных графов на независимое множество и подграф максимальной степени не более~$1$
\jour Сиб. матем. журн.
\yr 2011
\vol 52
\issue 5
\pages 1004--1010
\mathnet{http://mi.mathnet.ru/smj2253}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=2908122}
\transl
\jour Siberian Math. J.
\yr 2011
\vol 52
\issue 5
\pages 796--801
\crossref{https://doi.org/10.1134/S0037446611050041}
\isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000298650500004}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-80155142461}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/smj2253
  • http://mi.mathnet.ru/rus/smj/v52/i5/p1004

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    Эта публикация цитируется в следующих статьяx:
    1. Borodin O.V., Ivanova A.O., Montassier M., Raspaud A., “(k, 1)-coloring of sparse graphs”, Discrete Math, 312:6 (2012), 1128–1135  crossref  mathscinet  zmath  isi  elib  scopus
    2. Esperet L., Montassier M., Ochem P., Pinlou A., “A Complexity Dichotomy for the Coloring of Sparse Graphs”, J. Graph Theory, 73:1 (2013), 85–102  crossref  mathscinet  zmath  isi  elib  scopus
    3. Borodin O.V., Kostochka A., Yancey M., “On 1-Improper 2-Coloring of Sparse Graphs”, Discrete Math., 313:22 (2013), 2638–2649  crossref  mathscinet  zmath  isi  elib  scopus
    4. Dorbec P., Kaiser T., Montassier M., Raspaud A., “Limits of Near-Coloring of Sparse Graphs”, J. Graph Theory, 75:2 (2014), 191–202  crossref  mathscinet  zmath  isi  elib  scopus
    5. Borodin O.V., Kostochka A.V., “Defective 2-Colorings of Sparse Graphs”, J. Comb. Theory Ser. B, 104 (2014), 72–80  crossref  mathscinet  zmath  isi  elib  scopus
    6. Kim J., Kostochka A., Zhu X., “Improper Coloring of Sparse Graphs With a Given Girth, i: (0,1)-Colorings of Triangle-Free Graphs”, Eur. J. Comb., 42 (2014), 26–48  crossref  mathscinet  zmath  isi  elib  scopus
    7. Choi I., Raspaud A., “Planar Graphs With Girth At Least 5 Are (3,5)-Colorable”, Discrete Math., 338:4 (2015), 661–667  crossref  mathscinet  zmath  isi  elib  scopus
    8. Montassier M., Ochem P., “Near-Colorings: Non-Colorable Graphs and Np-Completeness”, Electron. J. Comb., 22:1 (2015), P1.57  mathscinet  zmath  isi  elib
    9. J. Kim, A. Kostochka, X. Zhu, “Improper coloring of sparse graphs with a given girth, II: constructions”, J. Graph Theory, 81:4 (2016), 403–413  crossref  mathscinet  zmath  isi  elib  scopus
    10. H. Choi, I. Choi, J. Jeong, G. Suh, “(1, k)-coloring of graphs with girth at least five on a surface”, J. Graph Theory, 84:4 (2017), 521–535  crossref  mathscinet  zmath  isi  scopus
    11. M. Zhang, M. Chen, Y. Wang, “A sufficient condition for planar graphs with girth 5 to be (1,7)-colorable”, J. Comb. Optim., 33:3 (2017), 847–865  crossref  mathscinet  zmath  isi  scopus
    12. Chen M., Yu W., Wang W., “On the Vertex Partitions of Sparse Graphs Into An Independent Vertex Set and a Forest With Bounded Maximum Degree”, Appl. Math. Comput., 326 (2018), 117–123  crossref  mathscinet  zmath  isi  scopus
    13. Wood D.R., “Defective and Clustered Graph Colouring”, Electron. J. Comb., 2018, DS23  zmath  isi
    14. Dross F., Montassier M., Pinlou A., “Partitioning Sparse Graphs Into An Independent Set and a Forest of Bounded Degree”, Electron. J. Comb., 25:1 (2018), P1.45  mathscinet  zmath  isi
    15. Hendrey K., Wood D.R., “Defective and Clustered Choosability of Sparse Graphs”, Comb. Probab. Comput., 28:5 (2019), 791–810  crossref  mathscinet  zmath  isi  scopus
  • Сибирский математический журнал Siberian Mathematical Journal
    Просмотров:
    Эта страница:237
    Полный текст:58
    Литература:38
    Первая стр.:1
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2020