commit 9b738794fd787a11d380e6f159cfce6b7738d7a1
parent e6ad6e9ec9cde5de4da422c8405a31872b791cf3
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Thu, 4 Dec 2025 08:41:56 +0100
Merge remote-tracking branch 'origin/master'
Diffstat:
4 files changed, 12 insertions(+), 0 deletions(-)
diff --git a/forest_minor_theorem b/forest_minor_theorem
@@ -0,0 +1,7 @@
+# Forest minor theorem
+
+proved by [Robertson_and_Seymour]: the [H_minor_free] [graphs] have bounded [pathwidth] iff H is a [forest]
+
+Discussed in [bonnet2025excluding], see also [kuhn2025computing]
+
+Up: [pathwidth]
diff --git a/graph_outerplanar b/graph_outerplanar
@@ -4,6 +4,8 @@ https://en.wikipedia.org/wiki/Outerplanar_graph
A [planar_graph] where all vertices are on the outer face of the drawing
+They are [3_colorable] and have [treewidth] at most 2; there are also [treewidth] bounds on outer-k-planar graphs [pyzik2025treewidth]
+
Up: [planar_graph]
Aliases: outerplanar graph, outerplanar graphs
diff --git a/pathwidth b/pathwidth
@@ -10,6 +10,8 @@ like [treewidth] but for [tree_decomposition] which is a [path]
- [pathwidth_obstruction]
+- [forest_minor_theorem]
+
Up: [width_measure], [path]
See also: [treewidth], [path_excentricity], [treelength]
diff --git a/planar_graph b/planar_graph
@@ -8,6 +8,7 @@ A [graph_undirected] that has a [plane_embedding], i.e., can be embedded on [pla
- [seymour1994call] "rat-catcher" "ratcatcher"
- open for [treewidth]
- [planar_language]
+- [hendrey2025optimal]: in an optimum-width [tree_decomposition] of a planar graph, the bags can be themselves assumed to have treewidth 3
[Theorems]:
