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

Abstract

A graph is ${\mathrm{ISK}}_4$-free if it contains no induced subdivision of $K_4$. Lévêque et al. [\emph{J. Combin. Theory Ser. B} \textbf{102} (2012) 924--947] conjectured that all ${\mathrm{ISK}}_4$-free graphs are 4-colorable. Chen et al. [\emph{J. Graph Theory} \textbf{96} (2021) 554--577] proved that $\{{\mathrm{ISK}}_4,\mathrm{diamond},\mathrm{bowtie}\}$-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{ISK}}_4,\mathrm{diamond},\mathrm{bowtie}\}$-free graphs and prove that such graphs are 3-colorable, which answers a question of Chen et al. [\emph{J. Graph Theory} \textbf{96} (2021) 554--577] affirmatively and extends a result of Chudnovsky et al. [\emph{J. Graph Theory} \textbf{92} (2019) 67--95]. Furthermore, our structural theorem yields a polynomial-time algorithm for decomposing $\{{\mathrm{ISK}}_4,\mathrm{diamond},\mathrm{bowtie}\}$-free graphs, and consequently a polynomial-time algorithm for coloring this class of graphs.

arXiv admin note: text overlap with arXiv:1704.08104 by other authors