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

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

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



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






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


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

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

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

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

a Институт математики им. С. Л. Соболева СО РАН
b Якутский государственный университет им. М. К. Аммосова
c University of Illinois at Urbana-Champaign
Список литературы:
Аннотация: Ориентированная k-раскраска вершин ориентированного графа H есть ориентированный гомоморфизм из H в некоторый k-вершинный турнир. Доказано, что любая ориентация графа с обхватом не менее 5 и максимальной средней степенью его подграфов менее 12/5 имеет ориентированную 5-раскраску. Как следствие, любая ориентация плоского или проективно плоского графа с обхватом не менее 12 имеет ориентированную 5-раскраску.
Статья поступила: 27.09.2005
Англоязычная версия:
Journal of Applied and Industrial Mathematics, 2007, Volume 1, Issue 1, Pages 9–17
DOI: https://doi.org/10.1134/S1990478907010024
Реферативные базы данных:
УДК: 517.71
Образец цитирования: О. В. Бородин, А. О. Иванова, А. В. Косточка, “Ориентированная 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://mathscinet.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{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-38449112627}
Образцы ссылок на эту страницу:
  • https://www.mathnet.ru/rus/da21
  • https://www.mathnet.ru/rus/da/v13/s1/i1/p16
  • Эта публикация цитируется в следующих 25 статьяx:
    1. Duffy Ch., Shane S.L., “On the Existence and Non-Existence of Improper Homomorphisms of Oriented and 2-Edge-Coloured Graphs to Reflexive Targets”, Discret. Math. Theor. Comput. Sci., 23:1 (2021), 6  mathscinet  isi
    2. Cranston D.W., Li J., “Circular Flows in Planar Graphs”, SIAM Discret. Math., 34:1 (2020), 497–519  crossref  mathscinet  zmath  isi  scopus
    3. Janusz Dybizbański, Pascal Ochem, Alexandre Pinlou, Andrzej Szepietowski, “Oriented cliques and colorings of graphs with low maximum degree”, Discrete Mathematics, 343:5 (2020), 111829  crossref
    4. 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
    5. Louis Esperet, Rémi de Joannis de Verclos, Tien-Nam Le, Stéphan Thomassé, “Additive bases and flows in graphs”, Electronic Notes in Discrete Mathematics, 61 (2017), 399  crossref
    6. 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
    7. 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
    8. 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
    9. 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
    10. 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
    11. 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
    12. 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
    13. 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
    14. Borodin O.V., “Colorings of Plane Graphs: a Survey”, Discrete Math., 313:4 (2013), 517–539  crossref  mathscinet  zmath  isi  elib  scopus
    15. 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
    16. 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
    17. 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
    18. Pascal Ochem, Alexandre Pinlou, “Oriented coloring of triangle-free planar graphs and 2-outerplanar graphs”, Electronic Notes in Discrete Mathematics, 37 (2011), 123  crossref
    19. 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
    20. 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
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Дискретный анализ и исследование операций
    Статистика просмотров:
    Страница аннотации:649
    PDF полного текста:140
    Список литературы:71
     
      Обратная связь:
     Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2025