Merge-width and First-Order Model Checking by Dreier, Toruńczyk

https://arxiv.org/abs/2502.18065

@article{MergeWidth2024,
archiveprefix = {arXiv},
author = {Jan Dreier and Szymon Toruńczyk},
month = {February},
primaryclass = {math.CO},
title = {Merge-width and First-Order Model Checking},
url = {https://arxiv.org/abs/2502.18065},
year = {2024},
}

• page 4 : merge-width – Merge-width. …
• page 6 : twin-width upper bounds merge-width by a computable function – Theorem 1.4. Graph classes of bounded twin-width have bounded merge-width.
• page 7 : bounded expansion upper bounds merge-width by a computable function – Theorem 1.6. Graph classes of bounded expansion have bounded merge-width.
• page 7 : merge-width upper bounds flip-width by a computable function – Theorem 1.7. Every class of bounded merge-width has bounded flip-width.
• page 7 : weakly sparse and merge width upper bounds bounded expansion by a computable function – Corollary 1.8. A graph class has bounded expansion if and only if it has bounded merge-width, and is weakly sparse (exclydes some biclique $K_{t,t}$ as a subgraph).
• page 7 : bounded expansion upper bounds weakly sparse and merge width by a computable function – Corollary 1.8. A graph class has bounded expansion if and only if it has bounded merge-width, and is weakly sparse (exclydes some biclique $K_{t,t}$ as a subgraph).