Product Structure of Graph Classes with Strongly Sublinear Separators

Kód výsledku v 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>

Výsledek na webu

<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>

Jazyk výsledku

angličtina

Název v původním jazyce

Product Structure of Graph Classes with Strongly Sublinear Separators

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

Product Structure of Graph Classes with Strongly Sublinear Separators

Popis výsledku anglicky

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.

Druh

J_ost - Ostatní články v recenzovaných periodicích

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

<a href="/cs/project/GA22-17398S" target="_blank" >GA22-17398S: Toky a cykly v grafech na plochách</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2025

Kód důvěrnosti údajů

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

Název periodika

Innovations in Graph Theory

ISSN

3050-743X

e-ISSN

3050-743X

Svazek periodika

2

Číslo periodika v rámci svazku

2

Stát vydavatele periodika

NL - Nizozemsko

Počet stran výsledku

32

Strana od-do

191-222

Kód UT WoS článku

—

EID výsledku v databázi Scopus

—