Stability of Hereditary Graph Classes Under Closure Operations
Identifikátory výsledku
Kód výsledku v IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F49777513%3A23520%2F13%3A43918750" target="_blank" >RIV/49777513:23520/13:43918750 - isvavai.cz</a>
Výsledek na webu
<a href="http://dx.doi.org/10.1002/jgt.21692" target="_blank" >http://dx.doi.org/10.1002/jgt.21692</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1002/jgt.21692" target="_blank" >10.1002/jgt.21692</a>
Alternativní jazyky
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.
Klasifikace
Druh
J<sub>x</sub> - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)
CEP obor
BA - Obecná matematika
OECD FORD obor
—
Návaznosti výsledku
Projekt
<a href="/cs/project/1M0545" target="_blank" >1M0545: Institut Teoretické Informatiky</a><br>
Návaznosti
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>Z - Vyzkumny zamer (s odkazem do CEZ)
Ostatní
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ů
Údaje specifické pro druh výsledku
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
—