Product Structure of Graph Classes with Strongly Sublinear Separators

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F25%3A10511830" target="_blank" >RIV/00216208:11320/25:10511830 - isvavai.cz</a>
Result on the web
<a href="https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=zUuIQNtjXl" target="_blank" >https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=zUuIQNtjXl</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.5802/igt.10" target="_blank" >10.5802/igt.10</a>

Result language
angličtina
Original language name
Product Structure of Graph Classes with Strongly Sublinear Separators
Original language description
We investigate the product structure of hereditary graph classes admitting strongly sublinear separators. We characterise such classes as subgraphs of the strong product of a star and a complete graph of strongly sublinear size. In a more precise result, we show that if any hereditary graph class admits separators, then for any fixed every -vertex graph in is a subgraph of the strong product of a graph with bounded tree-depth and a complete graph of size . This result holds with if we allow to have tree-depth . Moreover, using extensions of classical isoperimetric inequalties for grids graphs, we show the dependence on in our results and the above bound are both best possible. We prove that -vertex graphs of bounded treewidth are subgraphs of the product of a graph with tree-depth and a complete graph of size , which is best possible. Finally, we investigate the conjecture that for any hereditary graph class that admits separators, every -vertex graph in is a subgraph of the strong product of a graph with bounded tree-width and a complete graph of size . We prove this for various classes of interest.
Czech name
—
Czech description
—

Type
J<sub>ost</sub> - Miscellaneous article in a specialist periodical
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Project
<a href="/en/project/GA22-17398S" target="_blank" >GA22-17398S: Flows and cycles in graphs on surfaces</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Publication year
2025
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Similar results(10)