×
Diestel, Reinhard; Kühn, Daniela

Graph minor hierarchies. (English) Zbl 1055.05140

Discrete Appl. Math. 145, No. 2, 167-182 (2005).
Summary: We generalize tree-decompositions to decompositions modelled on graphs other than trees, and study how such more general decompositions might be used to establish structural complexity hierarchies of graph properties.

Cited in 7 Documents

MSC:

05C83 Graph minors
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

Keywords:

Graph minors; Hierarchy; Decomposition; Tree-width; Grid-width
Cite Review PDF
Full Text: DOI

References:

[1] Bondy, A.; Simonovits, M., Cycles of even length in graphs, J. Combin. Theory B, 16, 97-105 (1974) · Zbl 0283.05108
[2] Diestel, R., Graph Theory (2000), Springer: Springer Berlin · Zbl 0945.05002
[3] Diestel, R., Graph minors Ia short proof of the path width theorem, Combin. Probab. Comput., 4, 27-30 (1995) · Zbl 0829.05039
[4] Diestel, R., Relating subsets of a poset, and a partition theorem for WQOs, Order, 18, 275-279 (2001) · Zbl 1004.06002
[5] Diestel, R.; Gorbunov, K. Y.; Jensen, T. R.; Thomassen, C., Highly connected sets and the excluded grid theorem, J. Combin. Theory B, 75, 61-73 (1999) · Zbl 0949.05075
[6] R. Diestel, D. Kühn, Tree hierarchies, manuscripts 2000.; R. Diestel, D. Kühn, Tree hierarchies, manuscripts 2000.
[7] Erdős, P., Extremal problems in graph theory, (Fiedler, M., Theory of Graphs and its Applications, Proceedings of the Symposium, Smolenice, 1963 (1965), Academic Press: Academic Press New York), 29-36 · Zbl 0161.20501
[8] Robertson, N.; Seymour, P. D., Graph minors. I. Excluding a forest, J. Combin. Theory B, 35, 39-61 (1983) · Zbl 0521.05062
[9] Robertson, N.; Seymour, P. D., Graph minors. V. Excluding a planar graph, J. Combin. Theory B, 41, 92-114 (1986) · Zbl 0598.05055
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.