Comparing width parameters on graph classes

Brettell, Nick; Munaro, Andrea; Paulusma, Daniël; Yang, Shizhou

Abstract

We study how the relationship between non-equivalent width parameters changes once we restrict to some special graph class. As width parameters we consider treewidth, clique-width, twin-width, mim-width, sim-width and tree-independence number, whereas as graph classes we consider Kt,t-subgraph-free graphs, line graphs and their common superclass, for t≥3, of Kt,t-free graphs. For Kt,t-subgraph-free graphs, we extend a known result of Gurski and Wanke (2000) and provide a complete comparison, showing in particular that treewidth, clique-width, mim-width, sim-width and tree-independence number are all equivalent. For line graphs, we extend a result of Gurski and Wanke (2007) and also provide a complete comparison, showing in particular that clique-width, mim-width, sim-width and tree-independence number are all equivalent, and bounded if and only if the class of root graphs has bounded treewidth. For Kt,t-free graphs, we provide an almost-complete comparison, leaving open only one missing case. We show in particular that Kt,t-free graphs of bounded mim-width have bounded tree-independence number, and obtain structural and algorithmic consequences of this result, such as a proof of a special case of a recent conjecture of Dallard, Milanič and Štorgel. Finally, we consider the question of whether boundedness of a certain width parameter is preserved under graph powers. We show that this question has a positive answer for sim-width precisely in the case of odd powers.

Citation

Brettell, N., Munaro, A., Paulusma, D., & Yang, S. (2025). Comparing width parameters on graph classes. European Journal of Combinatorics, 127, Article 104163. https://doi.org/10.1016/j.ejc.2025.104163

• Journal Article Type: Article
• Acceptance Date: Apr 18, 2025
• Online Publication Date: May 3, 2025
• Publication Date: 2025-06
• Deposit Date: May 13, 2025
• Publicly Available Date: May 13, 2025
• Journal: European Journal of Combinatorics
• Print ISSN: 0195-6698
• Electronic ISSN: 1095-9971
• Publisher: Elsevier
• Peer Reviewed: Peer Reviewed
• Volume: 127
• Article Number: 104163
• DOI: https://doi.org/10.1016/j.ejc.2025.104163
• Public URL: https://durham-repository.worktribe.com/output/3947326