Аннотация:
Гипотеза о предписанной ациклической 5-раскрашиваемости плоских графов (О. В. Бородин и др., 2002) пока что подтверждена лишь для некоторых узких классов графов: с обхватом не менее 5 (Монтасьер, Ошам и Распо, 2006), без 4- и 5-циклов, или без 4- и 6-циклов (Монтасьер, Ванг и Распо, 2007), без 4-циклов и хордальных 6-циклов (Занг и Кзу, 2009), без 4-циклов и 3-циклов на расстоянии менее 3 (Чен и Ванг, 2008), а также без 4-циклов и пересекающихся 3-циклов (Чен и Распо, 2010). Ванг и Чен (2009) доказали, что плоские графы без 4-циклов предписанно ациклически 6-раскрашиваемы. В работе доказано, что плоский граф без 4-циклов предписанно ациклически 5-раскрашиваем, что является совместным усилением всех вышеперечисленных результатов.
Lin Sun, Guang Long Yu, Xin Li, “Every Graph Embedded on the Surface with Euler Characteristic Number ε = −1 is Acyclically 11-choosable”, Acta. Math. Sin.-English Ser., 39:11 (2023), 2247
Juan Wang, Lian Ying Miao, Jin Bo Li, Yun Long Liu, “Acyclic Choosability of Graphs with Bounded Degree”, Acta. Math. Sin.-English Ser., 38:3 (2022), 560
Sun L., “Acyclic 6-Choosability of Planar Graphs Without 5-Cycles and Adjacent 4-Cycles”, Acta. Math. Sin.-English Ser., 37:6 (2021), 992–1004
Yanfang He, Min Chen, Yingcai Sun, “On acyclic 4-choosability of planar graphs without cycles of length 4, 7 and 9”, Discrete Mathematics, 344:8 (2021), 112476
Sun Y., Chen M., “Acyclic 4-Choosability of Planar Graphs Without 4-Cycles”, Czech. Math. J., 70:1 (2020), 161–178
Juan Wang, Lianying Miao, Wenyao Song, “Acyclic L-coloring of graphs with maximum degrees 5 and 6”, Discrete Mathematics, 343:1 (2020), 111584
Sun Y., Chen M., Chen D., “Acyclic 4-Choosability of Planar Graphs Without Intersecting Short Cycles”, Discret. Math. Algorithms Appl., 10:1 (2018), 1850014
Sun L., “A Sufficient Condition For Acyclic 5-Choosability of Planar Graphs Without 5-Cycles”, Bull. Korean. Math. Soc., 55:2 (2018), 415–430
Cranston D.W., West D.B., “An Introduction to the Discharging Method Via Graph Coloring”, Discrete Math., 340:4 (2017), 766–793
Wang WeiFan, Zhang Ge, Chen Min, “Acyclic 6-Choosability of Planar Graphs Without Adjacent Short Cycles”, Sci. China-Math., 57:1 (2014), 197–209
Borodin O.V., Ivanova A.O., “Acyclic 4-Choosability of Planar Graphs with No 4- and 5-Cycles”, J. Graph Theory, 72:4 (2013), 374–397
Borodin O.V., “Colorings of Plane Graphs: a Survey”, Discrete Math., 313:4 (2013), 517–539
Chen M., Raspaud A., “Planar Graphs Without 4-and 5-Cycles Are Acyclically 4-Choosable”, Discrete Appl. Math., 161:7-8 (2013), 921–931
Weifan Wang, Yuehua Bu, Handbook of Combinatorial Optimization, 2013, 2095
Borodin O.V., Ivanova A.O., “Acyclic 4-Choosability of Planar Graphs Without Adjacent Short Cycles”, Discrete Math., 312:22 (2012), 3335–3341