|
|
Дискретн. анализ и исслед. опер., сер. 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{https://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
Citing articles on Google Scholar:
Russian citations,
English citations
Related articles on Google Scholar:
Russian articles,
English articles
Эта публикация цитируется в следующих статьяx:
-
Ochem P., Pinlou A., “Oriented colorings of partial 2-trees”, Inform. Process. Lett., 108:2 (2008), 82–86
  -
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
 -
О. В. Бородин, А. О. Иванова, “Почти правильные 2-раскраски вершин разреженных графов”, Дискретн. анализ и исслед. опер., 16:2 (2009), 16–20 ; O. V. Borodin, A. O. Ivanova, “Near-proper vertex 2-colorings of sparse graphs”, J. Appl. Industr. Math., 4:1 (2010), 21–23
-
Pinlou A., “An oriented coloring of planar graphs with girth at least five”, Discrete Math., 309:8 (2009), 2108–2118
-
О. В. Бородин, А. О. Иванова, “Разбиение разреженных плоских графов на два подграфа малой степени”, Сиб. электрон. матем. изв., 6 (2009), 13–16
-
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
-
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
-
Borodin O.V., Ivanova A.O., Montassier M., Raspaud A., “(k, 1)-coloring of sparse graphs”, Discrete Math, 312:6 (2012), 1128–1135
-
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
-
Borodin O.V., “Colorings of Plane Graphs: a Survey”, Discrete Math., 313:4 (2013), 517–539
-
Marshall T.H., “Homomorphism Bounds for Oriented Planar Graphs of Given Minimum Girth”, Graphs Comb., 29:5 (2013), 1489–1499
-
Bonamy M. Leveque B. Pinlou A., “List Coloring the Square of Sparse Graphs with Large Degree”, Eur. J. Comb., 41 (2014), 128–137
-
Ochem P., Pinlou A., “Oriented Coloring of Triangle-Free Planar Graphs and 2-Outerplanar Graphs”, Graphs Comb., 30:2 (2014), 439–453
-
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
-
Bonamy M., Leveque B., Pinlou A., “2-Distance Coloring of Sparse Graphs”, J. Graph Theory, 77:3 (2014), 190–218
-
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
-
Guegan G., Ochem P., “Complexity Dichotomy For Oriented Homomorphism of Planar Graphs With Large Girth”, Theor. Comput. Sci., 596 (2015), 142–148
-
Sopena E., “Homomorphisms and Colourings of Oriented Graphs: An Updated Survey”, Discrete Math., 339:7, SI (2016), 1993–2005
-
Marshall T.H., “An Oriented 6-Coloring of Planar Graphs With Girth At Least 9”, Graphs Comb., 32:3 (2016), 1101–1116
-
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
|
| Просмотров: |
| Эта страница: | 472 | | Полный текст: | 108 | | Литература: | 44 |
|
Пользовательское соглашение