In $ 1976 $, Steinberg conjectured that every planar graph without $ 4 $- and $ 5 $-cycles is $ 3 $-colorable. This conjecture was proved false by Cohen-Addad et al in 2017. Erdős raised the following question: Is there an integer $ k $ such that every planar graph without cycles of length from $ 4 $ to $ k $ is $ 3 $-colorable? Borodin et al. proved that every planar graph without cycles of length from $ 4 $ to $ 7 $ is $ 3 $-colorable [Planar graphs without cycles of length from $ 4 $ to $ 7 $ are $ 3 $-colorable, J. Combin.Theory Ser. B, 93 (2005), 303–311]. However, the question whether every planar graph without cycles of length from $ 4 $ to $ 6 $ is $ 3 $-colorable is not answered yet and full of challenges. A $ 7 $-cycle is called a special $ 7 $-cycle if it shares an edge with another $ 7 $-cycle or $ 9 $-cycle. In this paper, we prove that every planar graph without cycles of length from $ 4 $ to $ 6 $ and without special $ 7 $-cycles is $ 3 $-colorable which is an improvement of Borodin's result.
Citation: Zuosong Liang, Danzhang Liao, Chunsong Bai. On the $ 3 $-coloring of planar graphs without cycles of length from $ 4 $ to $ 6 $[J]. AIMS Mathematics, 2026, 11(5): 12895-12909. doi: 10.3934/math.2026530
In $ 1976 $, Steinberg conjectured that every planar graph without $ 4 $- and $ 5 $-cycles is $ 3 $-colorable. This conjecture was proved false by Cohen-Addad et al in 2017. Erdős raised the following question: Is there an integer $ k $ such that every planar graph without cycles of length from $ 4 $ to $ k $ is $ 3 $-colorable? Borodin et al. proved that every planar graph without cycles of length from $ 4 $ to $ 7 $ is $ 3 $-colorable [Planar graphs without cycles of length from $ 4 $ to $ 7 $ are $ 3 $-colorable, J. Combin.Theory Ser. B, 93 (2005), 303–311]. However, the question whether every planar graph without cycles of length from $ 4 $ to $ 6 $ is $ 3 $-colorable is not answered yet and full of challenges. A $ 7 $-cycle is called a special $ 7 $-cycle if it shares an edge with another $ 7 $-cycle or $ 9 $-cycle. In this paper, we prove that every planar graph without cycles of length from $ 4 $ to $ 6 $ and without special $ 7 $-cycles is $ 3 $-colorable which is an improvement of Borodin's result.
| [1] | H. L. Abbott, B. Zhou, On small faces in 4-critical graphs, Ars Comb., 32 (1991), 203–207. |
| [2] | O. V. Borodin, To the paper of H. L. Abbott and B. Zhou, On 4-critical planar graphs, Ars Comb., 43 (1996), 191–192. |
| [3] |
O. V. Borodin, Structural properties of plane graphs without adjacent triangles and an application to 3-colorings, J. Graph Theor., 21 (1996), 183–186. https://doi.org/10.1002/(SICI)1097-0118(199602)21:2<183::AID-JGT7>3.0.CO;2-N doi: 10.1002/(SICI)1097-0118(199602)21:2<183::AID-JGT7>3.0.CO;2-N
|
| [4] |
O. V. Borodin, A. N. Glebov, A. Raspaud, M. R. Salavatipour, Planar graphs without cycles of length from $4$ to $7$ are $3$-colorable, J. Comb. Theory B, 93 (2005), 303–311. https://doi.org/10.1016/j.jctb.2004.11.001 doi: 10.1016/j.jctb.2004.11.001
|
| [5] |
O. V. Borodin, A. N. Glebov, M. Montassier, A. Raspaud, Planar graphs without 5- and $7$-cycles and without adjacent triangles are $3$-colorable, J. Comb. Theory B, 99 (2009), 668–673. https://doi.org/10.1016/j.jctb.2008.11.001 doi: 10.1016/j.jctb.2008.11.001
|
| [6] |
V. Cohen-Addad, M. Hebdige, D. Kral, Z. Li, E. Salgado, Steinberg's conjecture is false, J. Comb. Theory B, 122 (2017) 452–456. https://doi.org/10.1016/j.jctb.2016.07.006 doi: 10.1016/j.jctb.2016.07.006
|
| [7] |
L. Jin, Y. Kang, M. Schubert, Y. Wang, Planar graphs without $4$- and $5$-cycles and without ext-triangular $7$-cycles are $3$-colorable, SIAM J. Discrete Math., 31 (2017), 1836–1847. https://doi.org/10.1137/16M1086418 doi: 10.1137/16M1086418
|
| [8] |
D. P. Sanders, Y. Zhao, A note on the three color problem, Graph. Combinator., 11 (1995), 91–94. https://doi.org/10.1007/BF01787424 doi: 10.1007/BF01787424
|
| [9] |
B. Xu, On 3-colorable plane graphs without 5- and 7-cycles, J. Comb. Theory B, 96 (2006), 958–963. https://doi.org/10.1016/j.jctb.2006.02.005 doi: 10.1016/j.jctb.2006.02.005
|
Figures(11)
Zuosong Liang, Danzhang Liao, Chunsong Bai. On the $ 3 $-coloring of planar graphs without cycles of length from $ 4 $ to $ 6 $[J]. AIMS Mathematics, 2026, 11(5): 12895-12909. doi: 10.3934/math.2026530
DownLoad: