ℋ-Clique-Width and a Hereditary Analogue of Product Structure
| Autoři | |
|---|---|
| Rok publikování | 2024 |
| Druh | Článek ve sborníku |
| Konference | 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024) |
| Fakulta / Pracoviště MU | |
| Citace | |
| Doi | http://dx.doi.org/10.4230/LIPIcs.MFCS.2024.61 |
| Klíčová slova | product structure; hereditary class; clique-width; twin-width |
| Popis | We introduce a novel generalization of the notion of clique-width which aims to bridge the gap between classical hereditary width measures and the recently introduced graph product structure theory. Bounding the new H-clique-width, in the special case of H being the class of paths, is equivalent to admitting a hereditary (i.e., induced) product structure of a path times a graph of bounded clique-width. Furthermore, every graph admitting the usual (non-induced) product structure of a path times a graph of bounded tree-width, has bounded H-clique-width and, as a consequence, it admits the usual product structure in an induced way. We prove further basic properties of H-clique-width in general. |
| Související projekty: |