Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
10151219 | Discrete Applied Mathematics | 2018 | 5 Pages |
Abstract
mim-width is a recent graph width measure that has seen applications in graph algorithms and problems related to propositional satisfiability. In this paper, we show linear lower bounds for the mim-width of strongly chordal split graphs, co-comparability graphs and circle graphs. This improves and refines lower bounds that were known before, some of them only conditionally. In the case of strongly chordal graphs not even a conditional lower bound was known before. All of the bounds given are optimal up to constants.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Stefan Mengel,