Forbidden graphs for tree-depth

Result code in 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>
Result on the web
<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>

Result language
angličtina
Original language name
Forbidden graphs for tree-depth
Original language description
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.
Czech name
—
Czech description
—

Type
J<sub>x</sub> - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)
CEP classification
BA - General mathematics
OECD FORD branch
—

Project
<a href="/en/project/1M0545" target="_blank" >1M0545: Institute for Theoretical Computer Science</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

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

Similar results(10)