zbMATH — the first resource for mathematics

Forbidden graphs for tree-depth. (English) Zbl 1239.05062
Summary: For every \(k\geq 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)\to {1,\ldots ,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 \(\mathcal G_{k}\)) that are minimal with respect to the minor/subgraph/induced subgraph relation (obstructions of \(\mathcal G_{k}\)). We determine these sets for \(k\leq 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 \(\mathcal G_{k}\)) and we prove that there are exactly \(\frac{1}{2}2^{2^{k - 1}-k}(1+2^{2^{k - 1}-k})\). Finally, we prove that each obstruction of \(G_{k}\) has at most \(2^{2^{k - 1}}\) vertices.

05C15 Coloring of graphs and hypergraphs
05C05 Trees
Full Text: DOI
[1] Bodlaender, H.L.; Deogun, J.S.; Jansen, K.; Kloks, T.; Kratsch, D.; Müller, H.; Tuza, Z., 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] Giannopoulou, A.C.; Thilikos, D.M., Obstructions for tree-depth, (), 249-253 · Zbl 1273.05212
[5] Katchalski, M.; McCuaig, W.; Seager, S., Ordered colourings, Discrete math., 142, 1-3, 141-154, (1995) · Zbl 0842.05032
[6] Liu, J.W.H., The role of elimination trees in sparse factorization, SIAM J. matrix anal. appl., 11, 1, 134-172, (1990) · Zbl 0697.65013
[7] Nešetřil, J.; Ossona de Mendez, P., Linear time low tree-width partitions and algorithmic consequences, (), 391-400 · Zbl 1301.05268
[8] Nešetřil, J.; Ossona de Mendez, P., Tree-depth, subgraph coloring and homomorphism bounds, European J. combin., 27, 6, 1022-1041, (2006) · Zbl 1089.05025
[9] Nešetřil, J.; Ossona de Mendez, P., Grad and classes with bounded expansion. I. decompositions, European J. combin., 29, 3, 760-776, (2008) · Zbl 1156.05056
[10] Nešetřil, J.; Ossona de Mendez, P., Grad and classes with bounded expansion. II. algorithmic aspects, European J. combin., 29, 3, 777-791, (2008) · Zbl 1185.05131
[11] Nešetřil, J.; Ossona de Mendez, P., Grad and classes with bounded expansion. III. restricted graph homomorphism dualities, European J. combin., 29, 4, 1012-1024, (2008) · Zbl 1213.05240
[12] Parsons, T.D., The search number of a connected graph, (), 549-554 · Zbl 0418.05022
[13] Robertson, N.; Seymour, P.D., Graph minors. XX. wagner’s conjecture, J. combin. theory ser. B, 92, 2, 325-357, (2004) · Zbl 1061.05088
[14] Rué, J.; Stavropoulos, K.S.; Thilikos, D.M., Outerplanar obstructions for feedback vertex set, (), 167-171 · Zbl 1273.05213
[15] Takahashi, A.; Ueno, S.; Kajitani, Y., Minimal acyclic forbidden minors for the family of graphs with bounded path-width, Discrete math., 127, 1-3, 293-304, (1994) · Zbl 0795.05123
[16] Thilikos, D.M., Algorithms and obstructions for linear-width and related search parameters, Discrete appl. math., 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.