Publications
Sort:
Open Access Research Article Issue
On the 3-coloring of planar graphs without cycles of length from 4 to 6
AIMS Mathematics 2026, 11(5): 12895-12909
Published: 15 May 2026
Abstract PDF (456.6 KB) Collect
Downloads:4

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.

Total 1