Linear rankwidth meets stability

Result code in 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>

Result on the web

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

Result language

angličtina

Original language name

Linear rankwidth meets stability

Original language description

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.

Czech name

—

Czech description

—

Type

D - Article in proceedings

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/GBP202%2F12%2FG061" target="_blank" >GBP202/12/G061: Center of excellence - Institute for theoretical computer science (CE-ITI)</a><br>

Continuities

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

Publication year

2020

Confidentiality

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

Article name in the collection

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

ISBN

978-1-61197-599-4

ISSN

—

e-ISSN

—

Number of pages

20

Pages from-to

1180-1199

Publisher name

ASSOC COMPUTING MACHINERY

Place of publication

NEW YORK

Event location

Salt Lake City

Event date

Jan 5, 2020

Type of event by nationality

WRD - Celosvětová akce

UT code for WoS article

000554408101016