New restrictions on defective coloring with applications to Steinberg-type graphs (Q2185826): Difference between revisions

Planar graphs without 4-cycles or 5-cycles are called Steinberg-type graphs. In 1976, R. Steinberg conjectured that such graphs are properly 3-colorable. Recently, Steinberg's conjecture was demonstrated to be false in [\textit{V. Cohen-Addad} et al., J. Comb. Theory, Ser. B 122, 452--456 (2017; Zbl 1350.05018)]. However, \textit{O. Hill} et al. showed that Steinberg-type graphs are (3, 0, 0)-defective colorable in [Discrete Math. 313, No. 20, 2312--2317 (2013; Zbl 1281.05055)]. The present paper introduces a stronger form of defective graph coloring that places limits on the permitted defects in a coloring. Using the strength of this new type of coloring, the authors prove the current closest result to Steinberg's original conjecture and show that the counterexample given by Cohen-Addad et al. [loc. cit.] is colorable with this stronger form of defective 3-coloring.