The 3-Coloring of Planar Graphs with Adjacent Triangles

Abstract

Erdős raised the following problem according to Steinberg’s conjecture: Is there an integer such that every planar graph without cycles of length from 4 to $k$ is 3-colorable. By far, the result about the problem was improved to $k≤7$ by Borodin et al. However, by permitting the existence of adjacent triangles except $K_4$, for an arbitrary integer $k≥5,$ there exists a planar graph without cycles of length from 5 to $k$ such that $G$ is not 3-colorable. Let $d$ denote the minimum distance between two diamonds in $G$, where a diamond is the union of two adjacent triangles. In this paper, we prove that a planar graph $G$ with $d≥2$ and without cycles of length from 5 to 18 is 3-colorable. The reader is invited to find the smallest integer $k$ such that a planar graph $G$ with $d≥2$ and without cycles of length from 5 to $k$ is 3-colorable.