On the structures of {diamond, bowtie}-free graphs that do not contain an induced subdivision of $K_4$

A graph is ${\mathrm{I}\mathrm{S}\mathrm{K}}_4$-free if it contains no induced subdivision of $K_4$. Lévêque et al. [\emph{J. Combin. Theory Ser. B} $\mathbf{\text{102}}$ (2012) 924–947] conjectured that all ${\mathrm{I}\mathrm{S}\mathrm{K}}_4$-free graphs are 4-colorable. Chen et al. [\emph{J. Graph Theory} $\mathbf{\text{96}}$ (2021) 554–577] proved that $\{{\mathrm{I}\mathrm{S}\mathrm{K}}_4,\mathrm{d}\mathrm{i}\mathrm{a}\mathrm{m}\mathrm{o}\mathrm{n}\mathrm{d},\mathrm{b}\mathrm{o}\mathrm{w}\mathrm{t}\mathrm{i}\mathrm{e}\}$-free graphs are 4-colorable and asked whether such graphs are 3-colorable, where a diamond is $K_4$ minus one edge and a bowtie consists of two triangles sharing a vertex. In this paper, we characterize the structures of $\{{\mathrm{I}\mathrm{S}\mathrm{K}}_4,\mathrm{d}\mathrm{i}\mathrm{a}\mathrm{m}\mathrm{o}\mathrm{n}\mathrm{d},\mathrm{b}\mathrm{o}\mathrm{w}\mathrm{t}\mathrm{i}\mathrm{e}\}$-free graphs and prove that such graphs are 3-colorable, which answers a question of Chen et al. [\emph{J. Graph Theory} $\mathbf{\text{96}}$ (2021) 554–577] affirmatively and extends a result of Chudnovsky et al. [\emph{J. Graph Theory} $\mathbf{\text{92}}$ (2019) 67–95]. Furthermore, our structural theorem yields a polynomial-time algorithm for decomposing $\{{\mathrm{I}\mathrm{S}\mathrm{K}}_4,\mathrm{d}\mathrm{i}\mathrm{a}\mathrm{m}\mathrm{o}\mathrm{n}\mathrm{d},\mathrm{b}\mathrm{o}\mathrm{w}\mathrm{t}\mathrm{i}\mathrm{e}\}$-free graphs, and consequently a polynomial-time algorithm for coloring this class of graphs.