(1,0,0)-colorability of planar graphs without cycles of length 4 or 6

Discrete Mathematics - Tập 345 - Trang 112758 - 2022
Yingli Kang1, Ligang Jin2, Peipei Liu3, Yingqian Wang2
1Department of Mathematics, Jinhua Polytechnic, Western Haitang Road 888, 321017 Jinhua, China
2Department of Mathematics, Zhejiang Normal University, Yingbin Road 688, 321004 Jinhua, China
3Hangzhou Weike software engineering Co. Ltd., Western Wenyi Road 998, 310012 Hangzhou, China

Tài liệu tham khảo

Abbott, 1991, On small faces in 4-critical graphs, Ars Comb., 32, 203 Borodin, 1996, Structural properties of plane graphs without adjacent triangles and an application to 3-colorings, J. Graph Theory, 21, 183, 10.1002/(SICI)1097-0118(199602)21:2<183::AID-JGT7>3.0.CO;2-N Borodin, 2005, Planar graphs without cycles of length from 4 to 7 are 3-colorable, J. Comb. Theory, Ser. B, 93, 303, 10.1016/j.jctb.2004.11.001 Bu, 2013, (1, 1,0)-coloring of planar graphs without cycles of length 4 and 6, Discrete Math., 313, 2737, 10.1016/j.disc.2013.08.005 Chen, 2016, Planar graphs without cycles of length 4 or 5 are (2,0,0)-colorable, Discrete Math., 339, 886, 10.1016/j.disc.2015.10.029 Cohen-Addad, 2017, Steinberg's Conjecture is false, J. Comb. Theory, Ser. B, 122, 452, 10.1016/j.jctb.2016.07.006 Cowen, 1986, Defective colorings of graphs in surfaces: partitions into subgraphs of bounded valency, J. Graph Theory, 10, 187, 10.1002/jgt.3190100207 Cranston Grötzsch, 1959, Ein Dreifarbensatz für dreikreisfreie Netze auf der Kugel, Wiss. Z., Martin-Luther-Univ. Halle-Wittenb., Math.-Nat.wiss. Reihe, 8, 109 Hill, 2013, Planar graphs without cycles of length 4 or 5 are (3, 0,0)-colorable, Discrete Math., 313, 2312, 10.1016/j.disc.2013.06.009 Hill, 2013, A relaxation of Steinberg's conjecture, SIAM J. Discrete Math., 27, 584, 10.1137/120888752 Jin, 2017, Plane graphs without 4- and 5-cycles and without ext-triangular 7-cycles are 3-colorable, SIAM J. Discrete Math., 31, 1836, 10.1137/16M1086418 Kang, 2016, The 3-colorability of planar graphs without cycles of length 4, 6 and 9, Discrete Math., 339, 299, 10.1016/j.disc.2015.08.023 Kang, 2015, Distance constraints on short cycles for 3-colorability of planar graphs, Graphs Comb., 31, 1497, 10.1007/s00373-014-1476-3 Lu, 2009, On the 3-colorability of planar graphs without 4-, 7- and 9-cycles, Discrete Math., 309, 4596, 10.1016/j.disc.2009.02.030 Sanders, 1995, A note on the three color problem, Graphs Comb., 11, 91, 10.1007/BF01787424 Steinberg, 1993, The state of the three color problem, vol. 55, 211 Wang, 2013, Planar graphs without cycles of length from 4 to 6 are (1,0,0)-colorable, Sci. Sin., Math., 43, 1145, 10.1360/012012-70 Wang, 2013, Planar graph with cycles of length neither 4 nor 6 are (2,0,0)-colorable, Inf. Process. Lett., 113, 659, 10.1016/j.ipl.2013.06.001 Xu, 2009, On (3,1)⁎-coloring of plane graphs, SIAM J. Discrete Math., 23, 205, 10.1137/06066093X Xu, 2013, Improper colorability of planar graphs with cycles of length neither 4 nor 6, Sci. Sin., Math., 43, 15, 10.1360/012012-70 Xu, 2014, Every planar graph with cycles of length neither 4 nor 5 is (1, 1,0)-colorable, J. Comb. Optim., 28, 774, 10.1007/s10878-012-9586-4