About DML-CZ | FAQ | Conditions of Use | Math Archives | Contact Us
  Previous |  Up |  Next

Article

First Page Preview
Matoušek, Jiří ; Nešetřil, Jaroslav ; Thomas, Robin
On polynomial time decidability of induced-minor-closed classes. (English). Commentationes Mathematicae Universitatis Carolinae, vol. 29 (1988), issue 4, pp. 703-710
MSC: 05C99, 68E10, 68Q20, 68Q25, 68R10 | MR 982789 | Zbl 0668.68048
References:
[AP] S. ARNBORG A. PROSKUROWSKI: Linear time algorithms for NP-hard problems on graphs embedded in k-trees. submitted.
[AP1] S. ARNBORG A. PROSKUROWSKI: Characterization and recognition of partial 3-trees. SIAM 3. Alg. Disc. Math. Vol.7, No. 2 (1986), 305-314. MR 0830649
[FL] M. FELLOWS M. LANGSTON: Nonconstructive tools for proving polynomial-time decidability. to appear in JACM. MR 0963169
[KGK] J. KRATOCHVÍL J. GOLIAN P. KUČERA: String graphs. Academia, Prague (1987), p. 105.
[MT] J. MATOUŠEK R. THOMAS: Algorithms finding tree-decompositions of graphs. submitted.
[NT] J. NEŠETŘIL R. THOMAS: A note on spatial Representation of Graphs. Comment. Math. Univ. Carolinae 26 (1985), 655-659. MR 0831801
[RS1] N. ROBERTSON P. S. SEYMOUR: Graph Minors V. Excluding a planar graph. J. Combin. Theory, Ser. B 41 (1986), 92-114. MR 0854606
[RS2] N. ROBERTSON P. D. SEYMOUR: Graph Minors X. Obstructions to treedecomposition. submitted.
[RS3] N. ROBERTSON P. D. SEYMOUR: Graph Minors XIII. The disjoint paths problem. submitted.
[T] R. THOMAS: Graphs without $K_4$ and well-quasi-ordering. J. Combin. Theory, Ser. (B) 38 (1985), 240-247. MR 0796601
[W] K. WAGNER: Bemerkungen zu Hadwigers Vermutung. Math. Ann. 141 (1960), 433-451. MR 0121309 | Zbl 0096.17904
Partner of
EuDML logo