# zbMATH — the first resource for mathematics

Obstructions for tree-depth. (English) Zbl 1273.05212
Nešetřil, Jaroslav (ed.) et al., Extended abstracts of the 5th European conference on combinatorics, graph theory and applications, EuroComb’09, Bordeaux, France, September 7–11, 2009. Amsterdam: Elsevier. Electronic Notes in Discrete Mathematics 34, 249-253 (2009).
Summary: For every $$k \geq 0$$, we define $${\mathcal{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) \to \{1,\dots,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 class $$\mathsf{obs}({\mathcal{G}}_{k})$$ of minor-minimal elements not belonging in $${\mathcal{G}}_{k}$$ for every $$k \geq 0$$. We give a precise characterization of $${\mathcal{G}}_{k}$$, $$k \leq 3$$ and prove a structural lemma for creating graphs $$G \in \mathsf{obs}({\mathcal{G}}_{k})$$, $$k>0$$. As a consequence, we obtain a precise characterization of all acyclic graphs in $$\mathsf{obs}({\mathcal{G}}_{k})$$ and we prove that they are exactly $$\frac{1}{2}2^{2^{k-1}-k}\left(1+2^{2^{k-1}-k}\right)$$.
For the entire collection see [Zbl 1239.05008].

##### MSC:
 05C83 Graph minors 05C30 Enumeration in graph theory
Full Text:
##### References:
  Bodlaender, Hans L.; Deogun, Jitender S.; Jansen, Klaus; Kloks, Ton; Kratsch, Dieter; Müller, Haiko; Tuza, Zsolt, Rankings of graphs, SIAM J. discrete math., 11, 1, 168-181, (1998), (electronic) · Zbl 0907.68137  de la Torre, P.; Greenlaw, R.; Schäffer, A.A., Optimal edge ranking of trees in polynomial time, Algorithmica, 13, 6, 592-618, (1995) · Zbl 0826.68093  Deogun, J.S.; Kloks, T.; Kratsch, D.; Müller, H., On vertex ranking for permutation and other graphs, (), 747-758 · Zbl 0941.05516  Katchalski, Meir; McCuaig, William; Seager, Suzanne, Ordered colourings, Discrete math., 142, 1-3, 141-154, (1995) · Zbl 0842.05032  Liu, Joseph W.H., The role of elimination trees in sparse factorization, SIAM J. matrix anal. appl., 11, 1, 134-172, (1990) · Zbl 0697.65013  Nešetřil, Jaroslav; de Mendez, Patrice Ossona, Linear time low tree-width partitions and algorithmic consequences, (), 391-400 · Zbl 1301.05268  Nešetřil, Jaroslav; de Mendez, Patrice Ossona, Tree-depth, subgraph colouring and homomorphism bounds, European J. combin., 27, 6, 1022-1041, (2006) · Zbl 1089.05025  Nešetřil, Jaroslav; de Mendez, Patrice Ossona, Grad and classes with bounded expansion. I. decompositions, European J. combin., 29, 3, 760-776, (2008) · Zbl 1156.05056  Nešetřil, Jaroslav; de Mendez, Patrice Ossona, Grad and classes with bounded expansion. II. algorithmic aspects, European J. combin., 29, 3, 777-791, (2008) · Zbl 1185.05131  Nešetřil, Jaroslav; de Mendez, Patrice Ossona, Grad and classes with bounded expansion. III. restricted graph homomorphism dualities, European J. combin., 29, 4, 1012-1024, (2008) · Zbl 1213.05240  Parsons, T.D., The search number of a connected graph, Proceedings of the ninth southeastern conference on combinatorics, graph theory, and computing, Congress. numer., utilitas math., XXI, 549-554, (1978)  Robertson, Neil; Seymour, P.D., Graph minors. XX. Wagner’s conjecture, J. combin. theory ser. B, 92, 2, 325-357, (2004) · Zbl 1061.05088  Takahashi, Atsushi; Ueno, Shuichi; Kajitani, Yoji, Minimal acyclic forbidden minors for the family of graphs with bounded path-width, Discrete mathematics, 127, 1/3, 293-304, (1994) · Zbl 0795.05123  Thilikos, Dimitrios M., Algorithms and obstructions for linear-width and related search parameters, Discrete applied mathematics, 105, 239-271, (2000) · Zbl 0958.05124
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.