H-Clique-Width and a Hereditary Analogue of Product Structure
<|reference_start|>H-Clique-Width and a Hereditary Analogue of Product Structure: 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.<|reference_end|>
@article{hliněný2024hereditary,
    title={Hereditary Graph Product Structure Theory and Induced Subgraphs of
  Strong Products},
    author={Petr Hlinv{e}n'y and Jan Jedelsk'y},
    journal={arXiv preprint arXiv:2403.16789},
    year={2024},
    archivePrefix={arXiv},
    eprint={2403.16789},
    primaryClass={math.CO cs.DM}
}