Stability of Hereditary Graph Classes Under Closure Operations

Kód výsledku v IS VaVaI

RIV/49777513:23520/13:43918750 - isvavai.cz

Výsledek na webu

http://dx.doi.org/10.1002/jgt.21692

DOI - Digital Object Identifier

10.1002/jgt.21692

Jazyk výsledku

angličtina

Název v původním jazyce

Stability of Hereditary Graph Classes Under Closure Operations

Popis výsledku v původním jazyce

If C is a subclass of the class of claw-free graphs, then C is said to be stable if, for any graph G from C, the local completion of G at any vertex is also in C. If cl is a closure operation that turns a claw-free graph into a line graph by a series oflocal completions and C is stable, then cl(G) belongs to C for any graph G from C. We consider stability of hereditary classes of claw-free graphs defined in terms of a family of connected closed forbidden induced subgraphs. We characterize line graph preimages of graphs in families that yield stable classes, we identify minimal families that yield stable classes in the finite case, and we also give a general background for techniques for handling unstable induced hereditary classes by proving that their closure may be included into another (possibly stable) class.

Název v anglickém jazyce

Stability of Hereditary Graph Classes Under Closure Operations

Popis výsledku anglicky

If C is a subclass of the class of claw-free graphs, then C is said to be stable if, for any graph G from C, the local completion of G at any vertex is also in C. If cl is a closure operation that turns a claw-free graph into a line graph by a series oflocal completions and C is stable, then cl(G) belongs to C for any graph G from C. We consider stability of hereditary classes of claw-free graphs defined in terms of a family of connected closed forbidden induced subgraphs. We characterize line graph preimages of graphs in families that yield stable classes, we identify minimal families that yield stable classes in the finite case, and we also give a general background for techniques for handling unstable induced hereditary classes by proving that their closure may be included into another (possibly stable) class.

Druh

J_x - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)

CEP obor

BA - Obecná matematika

OECD FORD obor

—

Projekt

1M0545: Institut Teoretické Informatiky

Návaznosti

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

Rok uplatnění

2013

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

Journal of Graph Theory

ISSN

0364-9024

e-ISSN

—

Svazek periodika

74

Číslo periodika v rámci svazku

1

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

14

Strana od-do

67-80

Kód UT WoS článku

—

EID výsledku v databázi Scopus

—