Linear rankwidth meets stability

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F20%3A10422250" target="_blank" >RIV/00216208:11320/20:10422250 - isvavai.cz</a>

Výsledek na webu

<a href="https://doi.org/10.1137/1.9781611975994.72" target="_blank" >https://doi.org/10.1137/1.9781611975994.72</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1137/1.9781611975994.72" target="_blank" >10.1137/1.9781611975994.72</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Linear rankwidth meets stability

Popis výsledku v původním jazyce

Classes with bounded rankwidth are MSO-transductions of trees and classes with bounded linear rankwidth are MSO-transductions of paths. These results show a strong link between the properties of these graph classes considered from the point of view of structural graph theory and from the point of view of finite model theory. We take both views on classes with bounded linear rankwidth and prove structural and model theoretic properties of these classes: 1) Graphs with linear rankwidth at most r are linearly chi-bounded. Actually, they have bounded c-chromatic number, meaning that they can be colored with f(r) colors, each color inducing a cograph. 2) Based on a Ramsey-like argument, we prove for every proper hereditary family F of graphs (like cographs) that there is a class with bounded rankwidth that does not have the property that graphs in it can be colored by a bounded number of colors, each inducing a subgraph in 3) For C class with bounded linear rankwidth the following conditions are equivalent: a) C is stable, b) C excludes some half-graph as a semi-induced subgraph, c) C is a first-order transduction of a class with bounded pathwidth. These results open the perspective to study classes admitting low linear rankwidth covers.

Název v anglickém jazyce

Linear rankwidth meets stability

Popis výsledku anglicky

Classes with bounded rankwidth are MSO-transductions of trees and classes with bounded linear rankwidth are MSO-transductions of paths. These results show a strong link between the properties of these graph classes considered from the point of view of structural graph theory and from the point of view of finite model theory. We take both views on classes with bounded linear rankwidth and prove structural and model theoretic properties of these classes: 1) Graphs with linear rankwidth at most r are linearly chi-bounded. Actually, they have bounded c-chromatic number, meaning that they can be colored with f(r) colors, each color inducing a cograph. 2) Based on a Ramsey-like argument, we prove for every proper hereditary family F of graphs (like cographs) that there is a class with bounded rankwidth that does not have the property that graphs in it can be colored by a bounded number of colors, each inducing a subgraph in 3) For C class with bounded linear rankwidth the following conditions are equivalent: a) C is stable, b) C excludes some half-graph as a semi-induced subgraph, c) C is a first-order transduction of a class with bounded pathwidth. These results open the perspective to study classes admitting low linear rankwidth covers.

Druh

D - Stať ve sborníku

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/GBP202%2F12%2FG061" target="_blank" >GBP202/12/G061: Centrum excelence - Institut teoretické informatiky (CE-ITI)</a><br>

Návaznosti

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

Rok uplatnění

2020

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 statě ve sborníku

PROCEEDINGS OF THE THIRTY-FIRST ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS (SODA&apos;20)

ISBN

978-1-61197-599-4

ISSN

—

e-ISSN

—

Počet stran výsledku

20

Strana od-do

1180-1199

Název nakladatele

ASSOC COMPUTING MACHINERY

Místo vydání

NEW YORK

Místo konání akce

Salt Lake City

Datum konání akce

5. 1. 2020

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

000554408101016