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

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

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



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






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


Дискретн. анализ и исслед. опер., сер. 1, 2006, том 13, номер 1, страницы 16–32 (Mi da21)  

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

Ориентированная 5-раскраска вершин в разреженных графах

О. В. Бородинa, А. О. Ивановаb, А. В. Косточкаac

a Институт математики им. С. Л. Соболева СО РАН
b Якутский государственный университет им. М. К. Аммосова
c University of Illinois at Urbana-Champaign

Аннотация: Ориентированная $k$-раскраска вершин ориентированного графа $H$ есть ориентированный гомоморфизм из $H$ в некоторый $k$-вершинный турнир. Доказано, что любая ориентация графа с обхватом не менее 5 и максимальной средней степенью его подграфов менее 12/5 имеет ориентированную 5-раскраску. Как следствие, любая ориентация плоского или проективно плоского графа с обхватом не менее 12 имеет ориентированную 5-раскраску.

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

Англоязычная версия:
Journal of Applied and Industrial Mathematics, 2007, 1:1, 9–17

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

УДК: 517.71
Статья поступила: 27.09.2005

Образец цитирования: О. В. Бородин, А. О. Иванова, А. В. Косточка, “Ориентированная 5-раскраска вершин в разреженных графах”, Дискретн. анализ и исслед. опер., сер. 1, 13:1 (2006), 16–32; J. Appl. Industr. Math., 1:1 (2007), 9–17

Цитирование в формате AMSBIB
\RBibitem{BorIvaKos06}
\by О.~В.~Бородин, А.~О.~Иванова, А.~В.~Косточка
\paper Ориентированная 5-раскраска вершин в~разреженных графах
\jour Дискретн. анализ и исслед. опер., сер.~1
\yr 2006
\vol 13
\issue 1
\pages 16--32
\mathnet{http://mi.mathnet.ru/da21}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=2258901}
\zmath{https://zbmath.org/?q=an:1249.05112}
\transl
\jour J. Appl. Industr. Math.
\yr 2007
\vol 1
\issue 1
\pages 9--17
\crossref{https://doi.org/10.1134/S1990478907010024}
\scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-38449112627}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/da21
  • http://mi.mathnet.ru/rus/da/v13/s1/i1/p16

    ОТПРАВИТЬ: 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. Ochem P., Pinlou A., “Oriented colorings of partial 2-trees”, Inform. Process. Lett., 108:2 (2008), 82–86  crossref  mathscinet  zmath  isi  elib  scopus
    2. O. V. Borodin, S. G. Hartke, A. O. Ivanova, A. V. Kostochka, D. B. West, “Circular $(5,2)$-coloring of sparse graphs”, Сиб. электрон. матем. изв., 5 (2008), 417–426  mathnet  mathscinet
    3. О. В. Бородин, А. О. Иванова, “Почти правильные 2-раскраски вершин разреженных графов”, Дискретн. анализ и исслед. опер., 16:2 (2009), 16–20  mathnet  mathscinet  zmath; O. V. Borodin, A. O. Ivanova, “Near-proper vertex 2-colorings of sparse graphs”, J. Appl. Industr. Math., 4:1 (2010), 21–23  crossref
    4. Pinlou A., “An oriented coloring of planar graphs with girth at least five”, Discrete Math., 309:8 (2009), 2108–2118  crossref  mathscinet  zmath  isi  elib  scopus
    5. О. В. Бородин, А. О. Иванова, “Разбиение разреженных плоских графов на два подграфа малой степени”, Сиб. электрон. матем. изв., 6 (2009), 13–16  mathnet  mathscinet
    6. Borodin O.V., Ivanova A.O., Montassier M., Ochem P., Raspaud A., “Vertex decompositions of sparse graphs into an edgeless subgraph and a subgraph of maximum degree at most $k$”, J. Graph Theory, 65:2 (2010), 83–93  crossref  mathscinet  zmath  isi  elib  scopus
    7. Montassier M., Raspaud A., Zhu Xuding, “Decomposition of sparse graphs into two forests, one having bounded maximum degree”, Inform. Process. Lett., 110:20 (2010), 913–916  crossref  mathscinet  zmath  isi  elib  scopus
    8. 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
    9. Borodin O.V., Ivanova A.O., “List 2-facial 5-colorability of plane graphs with girth at least 12”, Discrete Math, 312:2 (2012), 306–314  crossref  mathscinet  zmath  isi  elib  scopus
    10. Borodin O.V., “Colorings of Plane Graphs: a Survey”, Discrete Math., 313:4 (2013), 517–539  crossref  mathscinet  zmath  isi  elib  scopus
    11. Marshall T.H., “Homomorphism Bounds for Oriented Planar Graphs of Given Minimum Girth”, Graphs Comb., 29:5 (2013), 1489–1499  crossref  mathscinet  zmath  isi  elib  scopus
    12. Bonamy M. Leveque B. Pinlou A., “List Coloring the Square of Sparse Graphs with Large Degree”, Eur. J. Comb., 41 (2014), 128–137  crossref  mathscinet  zmath  isi  elib  scopus
    13. Ochem P., Pinlou A., “Oriented Coloring of Triangle-Free Planar Graphs and 2-Outerplanar Graphs”, Graphs Comb., 30:2 (2014), 439–453  crossref  mathscinet  zmath  isi  elib  scopus
    14. Bonamy M. Leveque B. Pinlou A., “Graphs with Maximum Degree Delta >= 17 and Maximum Average Degree Less Than 3 Are List 2-Distance (Delta+2)-Colorable”, Discrete Math., 317 (2014), 19–32  crossref  mathscinet  zmath  isi  elib  scopus
    15. Bonamy M., Leveque B., Pinlou A., “2-Distance Coloring of Sparse Graphs”, J. Graph Theory, 77:3 (2014), 190–218  crossref  mathscinet  zmath  isi  elib  scopus
    16. Nesetril J., de Mendez P.O., “a Note on Circular Chromatic Number of Graphs With Large Girth and Similar Problems”, J. Graph Theory, 80:4 (2015), 268–276  crossref  mathscinet  zmath  isi  elib  scopus
    17. Guegan G., Ochem P., “Complexity Dichotomy For Oriented Homomorphism of Planar Graphs With Large Girth”, Theor. Comput. Sci., 596 (2015), 142–148  crossref  mathscinet  zmath  isi  elib  scopus
    18. Sopena E., “Homomorphisms and Colourings of Oriented Graphs: An Updated Survey”, Discrete Math., 339:7, SI (2016), 1993–2005  crossref  mathscinet  zmath  isi  elib  scopus
    19. Marshall T.H., “An Oriented 6-Coloring of Planar Graphs With Girth At Least 9”, Graphs Comb., 32:3 (2016), 1101–1116  crossref  mathscinet  zmath  isi  elib  scopus
    20. Esperet L., de Verclos Remi de Joannis, Le T.-N., Thomasse S., “Additive Bases and Flows in Graphs”, SIAM Discret. Math., 32:1 (2018), 534–542  crossref  mathscinet  zmath  isi  scopus
  • Дискретный анализ и исследование операций
    Просмотров:
    Эта страница:454
    Полный текст:102
    Литература:43
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2020