On algorithmic applications of sim-width and mim-width of $(H_1,H_2)$-free graphs

Mim-width and sim-width are among the most powerful graph width parameters, with sim-width more powerful than mim-width, which is in turn more powerful than clique-width. While several $\mathsf{N}\mathsf{P}$-hard graph problems become tractable for graph classes whose mim-width is bounded and quickly computable, no algorithmic applications of boundedness of sim-width are known. In [Kang et al., A width parameter useful for chordal and co-comparability graphs, Theoretical Computer Science, 704:1-17, 2017], it is asked whether $\text{textsc}IndependentSet$ and \textsc{$3$-Colouring} are $\mathsf{N}\mathsf{P}$-complete on graphs of sim-width at most $1$. We observe that, for each $k \in $\mathbb{N}$, \textsc{Listk$-Colouring} is polynomial-time solvable for graph classes whose sim-width is bounded and quickly computable. Moreover, we show that if the same holds for $\text{textsc}IndependentSet$, then \textsc{Independent $\mathcal{H}$-Packing} is polynomial-time solvable for graph classes whose sim-width is bounded and quickly computable. This problem is a common generalisation of $\text{textsc}IndependentSet$, $\text{textsc}InducedMatching$, $\text{textsc}DissociationSet$ and \textsc{$k$-Separator}. We also make progress toward classifying the mim-width of $(H_1,H_2)$-free graphs in the case $H_1$ is complete or edgeless. Our results solve some open problems in [Brettell et al., Bounding the mim-width of hereditary graph classes, Journal of Graph Theory, 99(1):117-151, 2022].