wiki_research

commit 207e37ace8fb86e7b60e292c25e20ab9057e6d02
parent 6f52d2facb37d584602e3f6bb87abc37c0f16fb0
Author: Antoine Amarilli <a3nm@a3nm.net>
Date:   Thu,  3 Sep 2026 12:07:37 +0200

Merge remote-tracking branch 'origin/master'

Diffstat:
claw
 | 
9
+++++++++
claw_free_graph
 | 
11
+++++++++++
crpq
 | 
1
+
database_repairs
 | 
2
+-
ecrpq
 | 
11
+++++++++++
graph_family
 | 
2
++
line_graph
 | 
2
+-
obdd
 | 
2
+-
repair_notions
 | 
10
+++++-----
triangle_free_graph
 | 
4
+++-

10 files changed, 45 insertions(+), 9 deletions(-)
diff --git a/claw b/claw
@@ -0,0 +1,9 @@
+# Claw
+
+A [star] with 3 branches
+
+Up: [star]
+
+Aliases: claws
+
+See also: [claw_free_graph]
diff --git a/claw_free_graph b/claw_free_graph
@@ -0,0 +1,11 @@
+# Claw free graph
+
+https://en.wikipedia.org/wiki/Claw-free_graph
+
+A [graph] that does not contain a [claw] as an [induced_subgraph]
+
+Up: [graph_family]
+
+Aliases: claw free, clawfree, clawfree graph, clawfree graphs, claw free graphs
+
+See also: [triangle_free_graph]
diff --git a/crpq b/crpq
@@ -12,6 +12,7 @@
 - [conjunctive_context_free_path_query]
 - [regular_query]
   - [regular_query_with_memory]
+- [ECRPQ]
 
 [Computational_problems]:
 - [CRPQ_containment]
diff --git a/database_repairs b/database_repairs
@@ -11,6 +11,6 @@ A modification of a [database] to obtain a [database] which satisfies some [inte
 
 Up: [database_theory]
 
-See also: [language_repair], [graph_modification], [query_repairs], [data_cleaning]
+See also: [language_repair], [graph_modification], [query_repairs], [data_cleaning], [database_minimal_repairs]
 
 Aliases: database repair, data repair, data repairs
diff --git a/ecrpq b/ecrpq
@@ -0,0 +1,11 @@
+# ECRPQ
+
+Extended [CRPQ], defined in [barcelo2012expressive]
+
+Supports length contraints on paths
+
+Also discussed in [freydenberger2013expressiveness] and in [figueira2022when]
+
+Up: [crpq]
+
+Aliases: Extended CRPQ, Extended CRPQs
diff --git a/graph_family b/graph_family
@@ -49,6 +49,8 @@ A (generally [infinite]) set of [graphs]
 
 - [graph_word_representable]
 
+- [claw_free_graph]
+
 May have the property of being [graph_class_hereditary]
 
 Up: [graph]
diff --git a/line_graph b/line_graph
@@ -4,7 +4,7 @@ https://en.wikipedia.org/wiki/Line_graph
 
 The *line graph* of an [undirected_graph] G = (V, E) is the [graph] G' where the [vertices] of G' are E and where there is an edge in G' connecting two edges of E if they share a vertex in G
 
-They can be recognized in [linear_time]
+Such graphs can be recognized in [linear_time]. They are always [claw_free]
 
 - For [hamiltonian_cycles], cf [edge_hamiltonian_cycle]
 - For [hamiltonian_paths], cf [edge_hamiltonian_path]
diff --git a/obdd b/obdd
@@ -15,6 +15,6 @@ Notion: [bdd_width]
 
 Up: [bdd]
 
-See also: [fbdd]
+See also: [fbdd], [linear_vtree]
 
 Aliases: OBDDs
diff --git a/repair_notions b/repair_notions
@@ -1,10 +1,10 @@
 # Repair notions
 
-- [subset_repair]
-- [optimal_subset_repair], a [subset_repair] that [optimizes] a cost
-- can also do [insertions] of [tuples] in some cases
-- [minimal_repairs]
-- [cell_repairs]
+- [database_minimal_repairs]
+  - [subset_repair]
+  - [optimal_subset_repair], a [subset_repair] that [optimizes] a cost
+  - can also do [insertions] of [tuples] in some cases
+  - [cell_repairs]
 
 Up: [database_repairs]
 
diff --git a/triangle_free_graph b/triangle_free_graph
@@ -4,8 +4,10 @@ They are known to have unbounded [chromatic_number]
 
 [Mantel's_theorem] gives bounds on their size
 
-[computational_problem] of recognizing them: see [triangle_detection]
+For the [computational_problem] of recognizing them: see [triangle_detection]
 
 Up: [triangle], [graph], [graph_h_free]
 
 Aliases: triangle-free graph, triangle free graph, triangle-free graphs, triangle free graphs 
+
+See also: [claw_free_graph]