A step towards the strong version of Havelʼs three color conjecture

AbstractIn 1970, Havel asked if each planar graph with the minimum distance, d∇, between triangles large enough is 3-colorable. There are 4-chromatic planar graphs with d∇=3 (Aksenov, Melʼnikov, and Steinberg, 1980). The first result in the positive direction of Havelʼs problem was made in 2003 by Borodin and Raspaud, who proved that every planar graph with d∇⩾4 and no 5-cycles is 3-colorable.Recently, Havelʼs problem was solved by Dvořák, Králʼ and Thomas in the positive, which means that there exists a constant d such that each planar graph with d∇⩾d is 3-colorable. (As far as we can judge, this d is very large.)We conjecture that the strongest possible version of Havelʼs problem (SVHP) is true: every planar graph with d∇⩾4 is 3-colorable. In this paper we prove that each planar graph with d∇⩾4 and without 5-cycles adjacent to triangles is 3-colorable. The readers are invited to prove a stronger theorem: every planar graph with d∇⩾4 and without 4-cycles adjacent to triangles is 3-colorable, which could possibly open way to proving SVHP