Hereditary Graph Product Structure and $\cal H$-clique-width
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866918487171006464 |
|---|---|
| author | Hliněný, Petr Jedelský, Jan |
| author_facet | Hliněný, Petr Jedelský, Jan |
| contents | We introduce H-clique-width, a new structural measure of graphs that aims to provide a hereditary analogue of the traditional graph product structure. The definition naturally generalises the ordinary clique-width concept. As a result, for a class H of graphs (such as the class of paths), the H-clique-width of a graph G equals the least integer t such that G is isomorphic to an induced subgraph of the strong product of a graph from H and a graph of clique-width t. We study basic properties of H-clique-width and compare it to other established structural parameters of graphs. Notably, we prove that the celebrated Planar graph product structure theorem by Dujmovic et al., and related graph product structure results, can all be formulated with the induced subgraph containment relation. In particular, every planar graph is isomorphic to an induced subgraph of the strong product of a path and a graph of tree-width 39. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_16789 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Hereditary Graph Product Structure and $\cal H$-clique-width Hliněný, Petr Jedelský, Jan Combinatorics Discrete Mathematics 68R10 We introduce H-clique-width, a new structural measure of graphs that aims to provide a hereditary analogue of the traditional graph product structure. The definition naturally generalises the ordinary clique-width concept. As a result, for a class H of graphs (such as the class of paths), the H-clique-width of a graph G equals the least integer t such that G is isomorphic to an induced subgraph of the strong product of a graph from H and a graph of clique-width t. We study basic properties of H-clique-width and compare it to other established structural parameters of graphs. Notably, we prove that the celebrated Planar graph product structure theorem by Dujmovic et al., and related graph product structure results, can all be formulated with the induced subgraph containment relation. In particular, every planar graph is isomorphic to an induced subgraph of the strong product of a path and a graph of tree-width 39. |
| title | Hereditary Graph Product Structure and $\cal H$-clique-width |
| topic | Combinatorics Discrete Mathematics 68R10 |
| url | https://arxiv.org/abs/2403.16789 |