A note on the Three Color Problem on planar graphs without 4- and 5-cycles and without ext-triangular 7-cycles |
| |
| Affiliation: | 1. School of Mathematics and Physics, Center for Applied Mathematics of Guangxi, Guangxi Minzu University, Nanning 530006, China;2. School of mathematics, Zunyi Normal University, Zunyi 563000, China;3. School of Finance and Mathematics, Huainan Normal University, Huainan 232038, China |
| |
| Abstract: | Steinberg conjectured in 1976 that every planar graph with no cycles of length four or five is 3-colorable. This conjecture is disproved by constructing a planar graph with no cycles of length four or five but intersecting triangles. Jin et al. proved that plane graphs without 4- and 5-cycles and without ext-triangular 7-cycles are 3-colorable [SIAM J. Discrete Math. 31 (3) (2017) 1836–1847]. In this paper, we point out a mistake of their proof and give an improved proof. |
| |
| Keywords: | Coloring 3-colorable Planar graph |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
