commit 536cd34e9c368205ba17690d2044ecf53efc75db
parent 3378ed2a1e8296f0bb6a0031b9368d6de63facd8
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Tue, 9 Sep 2025 07:28:00 +0200
commit with codex
Diffstat:
6 files changed, 23 insertions(+), 3 deletions(-)
diff --git a/graph_cubic b/graph_cubic
@@ -0,0 +1,9 @@
+# Cubic graph
+
+A [graph] where the [degree] of each [vertex] is 3
+
+Up: [maximal_degree]
+
+Aliases: cubic graph, cubic graphs
+
+See also: [degree_3_graph], [graph_cube]
diff --git a/tree_decomposition b/tree_decomposition
@@ -4,6 +4,7 @@
- [tree_decomposition_updating]
- [balancing_tree_decomposition]
- [tree_decomposition_linked]
+- [tree_decomposition_normalized]
See also: [treewidth]
diff --git a/treewidth b/treewidth
@@ -36,6 +36,10 @@ A [width_measure] on [graphs]
- [bidimensionality]
+## Questions
+
+- [treewidth_finite_presentation]
+
## Practical applications
[treewidth_practical]
diff --git a/treewidth_directed b/treewidth_directed
@@ -5,6 +5,6 @@ directed treewidth, when it is bounded then the k-[disjoint_paths] problem is tr
[kawarabayashi2022directed] shows that a [graph_directed] with high directed treewdith contains a [directed_grid] as [butterfly_minor]
- polynomial bounds known [hatzel2019polynomial]
-Up: [treewidth]
+Up: [treewidth], [width_measure_directed]
See also: [pathwidth_directed], [grid_minor_directed]
diff --git a/treewidth_finite_presentation b/treewidth_finite_presentation
@@ -0,0 +1,5 @@
+# Treewidth finite presentation
+
+studied in [doumane2024finite]
+
+Up: [treewidth]
diff --git a/twin_width b/twin_width
@@ -9,8 +9,9 @@ Recent generalization (2023-02): [flip_width]
- for [enumeration]: [gajarsky2022twin]
- recognition:
- - deciding whether the twin-width is at most 4 is [np_hard]
- - graphs of twin-width 0 or 1 can be identified i [ptime]
+ - deciding whether the twin-width is at most 4 is [NP_hard]
+ - graphs of twin-width 0 are precisely the [cographs] and can be recognized in [linear_time]
+ - graphs of twin-width 1 have been characterized and can be recognized in [linear_time]: [ahn2025twin]
- [Trees] have twin-width at most 2
- so twin-width is at most 2 plus the [feedback_edge_number]
