Revision #158 → #1273 · back to history
addedGraph minore040838337d7
addedWagner's theorem (planarity)4bd130217d84
addedRobertson–Seymour forbidden minor characterization2fe55a5f609a
addedPolynomial-time minor testing2d5bd449233d
addedEdge contractiond2f63c264ff2
addedMinor (formal)48a02c4983c1
addedOrder independence of contractions and deletionscabb628d6ed5
addedRank under deletion and contractioneeeafbbb4619
addedMinor-monotone function4d1e5b473b3d
addedH is a minor of Gd130b62945da
addedMinor relation is a partial orderc24b2dc5de2b
addedRobertson–Seymour well-quasi-ordering (Wagner's conjecture)907dd497d64c
addedGraph structure theoremee8e378745bb
addedH-minor-free graphs are sparse848d30df30e9
addedSeparator theorem for H-minor-free graphsfe4bfc3a0d21
addedTreewidth bound for H-minor-free graphsf3f18e78ba9e
addedHadwiger conjecturee995ea8d9aa0
addedCase k=5 is the four color theorem16189da037cf
addedSnark theorem01194fb9ea53
addedMinor-closed family7edd7629d25b
addedPlanar and surface-embeddable graphs are minor-closed6a8fe7617931
addedFinite forbidden minor characterization of minor-closed familiesf92453d829f7
addedWagner's theorem characterizing planar graphsfef9c0cd876b
addedBounded pathwidth iff forbidden minor is a forest0a0e6d99f611
addedBounded tree-depth iff forbidden disjoint union of pathsed709df8fa61
addedBounded treewidth iff forbidden minor is planar3fd53e6c1823
addedBounded local treewidth iff forbidden apex graph9507f775ac4d
addedSimplified structure theorem for crossing-number-one H0d85a7c19be2
addedWagner's characterization of K5-free graphs270589464427
addedTopological minordd3e6db57c7a
addedTopological minor is a minor50a3d168d5e1
addedConverse holds for maximum degree at most three27b423e21d88
addedTopological minor relation is not a well-quasi-orderingd68beab4a162
addedInduced minor4d406f36d784
addedInduced minor of a string graph is a string graph032d35987692
addedString graphs have infinitely many induced-minor obstaclesb32a26b6d1de
addedLifting operation8b11cf3e1f9b
addedImmersion minor (via lifting)c8559e1d6aa0
addedImmersion minor (edge-disjoint paths)56f94aaa6bd0
addedImmersion minor relation is a well-quasi-ordering256283f301e2
addedImmersion minors as planarizations5a4b23004810
addedShallow minor6dd28dfece5f
addedMinor via vertex-disjoint subtrees9a57a9cf1158
addedOdd minore57370cefd6b
addedForbidden odd minors need not be sparse142a45478826
addedBipartite minor6ca478aa7911
addedWagner's theorem for bipartite minors1a50bfdf5a77
addedMinor containment is NP-complete39846eb567b8
addedFixed H solvable in polynomial timee41780a054db
addedPolynomial-time recognition of minor-closed families2e9e7e488336
addedLinear-time test for fixed planar Heb9fe6e67250