Forbidden graphs for tree-depth

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F12%3A10125700" target="_blank" >RIV/00216208:11320/12:10125700 - isvavai.cz</a>

Výsledek na webu

<a href="http://dx.doi.org/10.1016/j.ejc.2011.09.014" target="_blank" >http://dx.doi.org/10.1016/j.ejc.2011.09.014</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1016/j.ejc.2011.09.014" target="_blank" >10.1016/j.ejc.2011.09.014</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Forbidden graphs for tree-depth

Popis výsledku v původním jazyce

For every k }= 0, we define G(k) as the class of graphs with tree-depth at most k, i.e. the class containing every graph G admitting a valid colouring rho : V(G) -> {1, ... , k} such that every (x, y)-path between two vertices where rho(x) = rho(y) contains a vertex z where rho(z) > rho(x). In this paper, we study the set of graphs not belonging in G(k) that are minimal with respect to the minor/subgraph/induced subgraph relation (obstructions of G(k)). We determine these sets for k {= 3 for each relation and prove a structural lemma for creating obstructions from simpler ones. As a consequence, we obtain a precise characterization of all acyclic obstructions of G(k) and we prove that there are exactly 1/2 2(2k-1-k)(1+2(2k-1-k)). Finally, we prove thateach obstruction of G(k) has at most 2(2k-1) vertices.

Název v anglickém jazyce

Forbidden graphs for tree-depth

Popis výsledku anglicky

For every k }= 0, we define G(k) as the class of graphs with tree-depth at most k, i.e. the class containing every graph G admitting a valid colouring rho : V(G) -> {1, ... , k} such that every (x, y)-path between two vertices where rho(x) = rho(y) contains a vertex z where rho(z) > rho(x). In this paper, we study the set of graphs not belonging in G(k) that are minimal with respect to the minor/subgraph/induced subgraph relation (obstructions of G(k)). We determine these sets for k {= 3 for each relation and prove a structural lemma for creating obstructions from simpler ones. As a consequence, we obtain a precise characterization of all acyclic obstructions of G(k) and we prove that there are exactly 1/2 2(2k-1-k)(1+2(2k-1-k)). Finally, we prove thateach obstruction of G(k) has at most 2(2k-1) vertices.

Druh

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

CEP obor

BA - Obecná matematika

OECD FORD obor

—

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)

Rok uplatnění

2012

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

European Journal of Combinatorics

ISSN

0195-6698

e-ISSN

—

Svazek periodika

33

Číslo periodika v rámci svazku

5

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

11

Strana od-do

969-979

Kód UT WoS článku

000301306200020

EID výsledku v databázi Scopus

—