commit ea0accc24cc2fd85ae66b140bcb8a940a6477bdd
parent b8ac383eeb801039197bed8c8f9f980116bebe2b
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Mon, 3 Mar 2025 18:48:49 +0100
commit with codex
Diffstat:
6 files changed, 57 insertions(+), 3 deletions(-)
diff --git a/arboricity b/arboricity
@@ -1,5 +1,10 @@
# Arboricity
+A [width_measure] on [undirected_graphs]: the minimum number of [spanning_forests] needed to cover all [edges] of the [graph]
+- equivalently, the [minimum] number of [forests] in which the [edges] can be partitioned
+
+A [planar_graph] has arboricity has arboricity at most 3
+
Connection between [arboricity] and [dynamic_data] in [lu2021towards]
- [chiba1985arboricity]
@@ -8,6 +13,8 @@ Connection between [arboricity] and [dynamic_data] in [lu2021towards]
- https://github.com/maxdan94/kmotif
- [ortmann2014triangle] algorithm for [triangle_listing]
-[bressan2022complexity]: optimality of the results of chiba for [graph_pattern_counting]
+[bressan2022complexity]: optimality of the results of [chiba1985arboricity] for [graph_pattern_counting]
Up: [width_measure]
+
+See also: [degeneracy], [thickness], [pseudoarboricity]
diff --git a/degeneracy b/degeneracy
@@ -3,7 +3,8 @@
https://en.wikipedia.org/wiki/Degeneracy_(graph_theory)
An [undirected_graph] is k-degenerate if every [subgraph] has at least one [vertex] of [degree] at most k
-- it does not make a difference whether we define this via [subgraphs] or via [induced_subgraphs], cf https://en.wikipedia.org/wiki/Degeneracy_(graph_theory)#Examples
+- it does not make a difference whether we define this via [subgraphs] or via [induced_subgraphs]
+ - cf https://en.wikipedia.org/wiki/Degeneracy_(graph_theory)#Examples
Special case: [2_degenerate_graphs]
@@ -11,6 +12,13 @@ Some [enumeration] and [counting] problems on graphs have been studied based on
Generalization to [relational_databases]: [partition_constraints] introduced in [deeds2025partition]
+The [arboricity] is no greater than the degeneracy, and the degeneracy is at most twice the [arboricity].
+ - source https://en.wikipedia.org/wiki/Degeneracy_(graph_theory)#Relation_to_other_graph_parameters
+
+The degeneracy of an [undirected_graph] is equal to the [maximum_degree] if and only if one of the [connected_components] is a [regular_graph] https://en.wikipedia.org/wiki/Degeneracy_(graph_theory)#Examples
+
+A [k_vertex_connected] graph has degeneracy at most k
+
Up: [width_measure]
-See also: [arboricity]
+See also: [arboricity], [thickness]
diff --git a/graph_orientation b/graph_orientation
@@ -5,3 +5,5 @@
- [constraint_graph_satisfiability]
Up: [computational_problem] on [graph]
+
+Aliases: oriented
diff --git a/graph_regular b/graph_regular
@@ -0,0 +1,16 @@
+# Graph regular
+
+A [graph] where all [vertices] have the same [degree]
+
+https://mathoverflow.net/questions/428212/perfect-matching-decomposition-algorithm-for-bipartite-regular-graphs
+- a [bipartite_graph] can be decomposed into edge-disjoint [perfect_matchings] iff the [graph] is regular
+- uses [halls_theorem] https://math.stackexchange.com/questions/4361540/if-g-is-n-regular-then-g-has-n-disjoint-perfect-matchings
+
+[Special_case]:
+- [2_regular]
+
+See also: [graph_matching_covered]
+
+Up: [graph]
+
+Aliases: regular graph
diff --git a/pseudoarboricity b/pseudoarboricity
@@ -0,0 +1,10 @@
+# Pseudoarboricity
+
+https://en.wikipedia.org/wiki/Pseudoforest#Algorithms
+
+The minimum number of [pseudoforests] in which the [edges] of an [undirected_graph] can be partitioned, or the minimum k such that the [edges] can be [oriented] to form a [directed_graph] with [outdegree] at most k
+- can be computed in [PTIME]
+
+See also: [arboricity]
+
+Up: [width_measure]
diff --git a/pseudoforest b/pseudoforest
@@ -0,0 +1,11 @@
+# Pseudoforest
+
+https://en.m.wikipedia.org/wiki/Pseudoforest
+
+[Undirected_graph] in which every [connected_component] has at most one [cycle]
+
+Up: [forest]
+
+Aliases: pseudoforests
+
+See also: [pseudoarboricity]
