Аннотация:
Ориентированная k-раскраска вершин ориентированного графа H есть ориентированный гомоморфизм из H в некоторый k-вершинный турнир. Доказано, что любая ориентация графа с обхватом не менее 5 и максимальной средней степенью его подграфов менее 12/5 имеет ориентированную 5-раскраску. Как следствие, любая ориентация плоского или проективно плоского графа с обхватом не менее 12 имеет ориентированную 5-раскраску.
Образец цитирования:
О. В. Бородин, А. О. Иванова, А. В. Косточка, “Ориентированная 5-раскраска вершин в разреженных графах”, Дискретн. анализ и исслед. опер., сер. 1, 13:1 (2006), 16–32; J. Appl. Industr. Math., 1:1 (2007), 9–17
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
Cranston D.W., Li J., “Circular Flows in Planar Graphs”, SIAM Discret. Math., 34:1 (2020), 497–519
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
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
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
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
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
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
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
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
Pascal Ochem, Alexandre Pinlou, “Oriented coloring of triangle-free planar graphs and 2-outerplanar graphs”, Electronic Notes in Discrete Mathematics, 37 (2011), 123
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