$\chi$-Boundedness and Neighbourhood Complexity of Bounded Merge-Width Graphs
$\chi$-Boundedness and Neighbourhood Complexity of Bounded Merge-Width Graphs
Merge-width, recently introduced by Dreier and Toru\'nczyk, 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 $\chi$-bounded, they satisfy the strong Erd\H{o}s-Hajnal property, and their neighbourhood complexity is linear.
Marthe Bonamy、Colin Geniet
计算技术、计算机技术
Marthe Bonamy,Colin Geniet.$\chi$-Boundedness and Neighbourhood Complexity of Bounded Merge-Width Graphs[EB/OL].(2025-04-11)[2025-06-08].https://arxiv.org/abs/2504.08266.点此复制
评论