Exploring the Weak Steinberg’s Conjecture

The Weak Steinberg’s Conjecture, a restriction on Steinberg’s Conjecture which was disproven in 2016, is an established and long-standing open problem in graph theory: Is every planar graph G containing no 4-, 5-, or 6-cycles vertex 3-colourable? If proven, forbidding 4- to 7-cycles in planar graphs suffices to ensure vertex 3-colourability. Otherwise, forbidding only 4- to 6-cycles is sufficient. We hypothesise that the Weak Steinberg’s Conjecture is false. In other words, not every planar graph G containing no 4-, 5-, and 6-cycles is vertex 3-colourable. Hence, two constructions of counterexamples to the Weak Steinberg’s Conjecture are outlined and attempted. By analysing counterexamples to related problems in past literature, we identified key subgraphs that provide these counterexamples their properties and applied them in our constructions. Our utilisation of these subgraphs to construct graphs with desired properties was successful. In the first attempt, we constructed a non- vertex 3-colourable graph without 4- and 5-cycles but it was nonplanar and contained a single 6-cycle. Our improved second attempt eliminated this 6-cycle: a nonplanar non- vertex 3-colourable graph without 4-, 5- and 6-cycles. Hence, the subgraphs outlined in our attempts may prove useful for future research into solving this open problem. If crossovers or quasi-edges satisfying Weak Steinberg’s Conjecture are developed in the future, our results may help finally disprove this conjecture.