English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

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 powerfulthan clique-width. While several $\mathsf{NP}$-hard graph problems becometractable for graph classes whose mim-width is bounded and quickly computable,no algorithmic applications of boundedness of sim-width are known. In [Kang etal., A width parameter useful for chordal and co-comparability graphs,Theoretical Computer Science, 704:1-17, 2017], it is asked whether\textsc{Independent Set} and \textsc{$3$-Colouring} are $\mathsf{NP}$-completeon graphs of sim-width at most $1$. We observe that, for each $k \in\mathbb{N}$, \textsc{List $k$-Colouring} is polynomial-time solvable for graphclasses whose sim-width is bounded and quickly computable. Moreover, we showthat if the same holds for \textsc{Independent Set}, then \textsc{Independent$\mathcal{H}$-Packing} is polynomial-time solvable for graph classes whosesim-width is bounded and quickly computable. This problem is a commongeneralisation of \textsc{Independent Set}, \textsc{Induced Matching},\textsc{Dissociation Set} and \textsc{$k$-Separator}. We also make progresstoward 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 etal., Bounding the mim-width of hereditary graph classes, Journal of GraphTheory, 99(1):117-151, 2022].

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