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].

05C83 Graph minors
05C30 Enumeration in graph theory
PDF BibTeX Cite
Full Text: DOI
[1] 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
[2] 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
[3] Deogun, J.S.; Kloks, T.; Kratsch, D.; Müller, H., On vertex ranking for permutation and other graphs, (), 747-758 · Zbl 0941.05516
[4] Katchalski, Meir; McCuaig, William; Seager, Suzanne, Ordered colourings, Discrete math., 142, 1-3, 141-154, (1995) · Zbl 0842.05032
[5] 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
[6] Nešetřil, Jaroslav; de Mendez, Patrice Ossona, Linear time low tree-width partitions and algorithmic consequences, (), 391-400 · Zbl 1301.05268
[7] 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
[8] 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
[9] 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
[10] 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
[11] 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)
[12] Robertson, Neil; Seymour, P.D., Graph minors. XX. Wagner’s conjecture, J. combin. theory ser. B, 92, 2, 325-357, (2004) · Zbl 1061.05088
[13] 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
[14] 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.