


























Merge-width, recently introduced by Dreier and Toruńczyk, is a common generalisation of bounded expansion classes and twin-width for which the first-order model checking problem remains tractable. We prove that a number of basic properties shared by bounded expansion and bounded twin-width graphs also hold for bounded merge-width graphs: they are $χ$-bounded, they satisfy the strong Erdős-Hajnal property, and their neighbourhood complexity is linear.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。