commit 80cabccb551f2add96735faa6ca99d5cf51946ea
parent 4a2cd9ce25b8ec8b865dcc5f22f9b2d6d6bb5f01
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Wed, 8 Jan 2025 13:50:03 +0100
commit with codex
Diffstat:
13 files changed, 84 insertions(+), 7 deletions(-)
diff --git a/edge_contraction b/edge_contraction
@@ -0,0 +1,9 @@
+# Edge contraction
+
+Given a [graph] G and an [edge] e, performing the *contraction* of e in G means merging the two [endpoints] e into one single vertex
+
+Up: [graph]
+
+Aliases: edge contractions, contraction, contractions
+
+See also: [contraction_sequence]
diff --git a/extremal_graph_theory b/extremal_graph_theory
@@ -10,4 +10,6 @@ https://en.wikipedia.org/wiki/Extremal_graph_theory
- [szemeredi_regularity_lemma]
+- [forbidden_subgraph_problem]
+
Up: [extremal_combinatorics] on [graph]
diff --git a/forbidden_graph_characterization b/forbidden_graph_characterization
@@ -0,0 +1,14 @@
+# Forbidden graph characterization
+
+https://en.wikipedia.org/wiki/Forbidden_graph_characterization
+(contains a list)
+
+Can be based on:
+
+- [subgraphs]
+- [induced_subgraphs]
+- [topological_minors]
+- [minors], see [forbidden_minor]
+- [induced_minors]
+
+See also: [graph_free]
diff --git a/forbidden_subgraph_problem b/forbidden_subgraph_problem
@@ -0,0 +1,7 @@
+# Forbidden subgraph problem
+
+https://en.wikipedia.org/wiki/Forbidden_subgraph_problem
+
+Largest number of [edges] in an n-[vertex] [undirected_graph] while being [graph_h_free]
+
+Up: [graph_h_free], [extremal_graph_theory]
diff --git a/graph_free b/graph_free
@@ -0,0 +1,11 @@
+# Graph free
+
+An [undirected_graph] that does not have a certain kind of structure
+
+- [graph_induced_h_free]
+- [graph_h_minor_free]
+- [graph_h_free]
+
+Up: [graph_family]
+
+See also: [forbidden_graph_characterization]
diff --git a/graph_h_free b/graph_h_free
@@ -1,9 +1,12 @@
# H-free graph
-An [undirected_graph] is *H-free* if it does not have an [undirected_graph] H as an [induced_minor]
+An [undirected_graph] is *H-free* if it does not have an [undirected_graph] H as a [subgraph]
Each [undirected_graph] H thus defines a [graph_family]
-- [graph_pk_free]
+- [triangle_free_graphs]
+- [forbidden_subgraph_problem]
-Up: [graph_family]
+Up: [graph_free]
+
+See also: [induced_h_free], [h_minor_free]
diff --git a/graph_h_minor_free b/graph_h_minor_free
@@ -6,6 +6,6 @@ Each [undirected_graph] H thus defines a [graph_family], which must be [sparse_g
discussed in https://en.wikipedia.org/wiki/Graph_minor
-Up: [graph_family]
+Up: [graph_free]
See also: [graph_h_free]
diff --git a/graph_induced_h_free b/graph_induced_h_free
@@ -0,0 +1,11 @@
+# induced-H-free graph
+
+An [undirected_graph] is *induced-H-free* if it does not have an [undirected_graph] H as an [induced_subgraph]
+
+Each [undirected_graph] H thus defines a [graph_family]
+
+- [graph_pk_free]
+
+Up: [graph_free]
+
+See also: [graph_h_free]
diff --git a/graph_minor b/graph_minor
@@ -1,6 +1,6 @@
# Graph minor
-- [contraction]
+- [edge_contraction]
[graph_minor_testing]
@@ -8,4 +8,4 @@ Up: [graph]
See also: [robertson_seymour], [topological_minor], [excluded_minor], [forbidden_minor], [induced_minor]
-Aliases: graph minors
+Aliases: graph minors, minor, minors
diff --git a/induced_minor b/induced_minor
@@ -0,0 +1,9 @@
+# Induced minor
+
+https://en.wikipedia.org/wiki/Graph_minor#Induced_minors
+
+An [undirected_graph] H that can be obtained from an [undirected_graph] G by taking an [induced_subgraph] and then doing [edge_contractions]
+
+See also: [graph_minor]
+
+Aliases: induced minors
diff --git a/induced_subgraph b/induced_subgraph
@@ -1,7 +1,9 @@
# Induced subgraph
-[subgraph] defined by taking a subset U of vertices and the edges between the vertices of U
+A [subgraph] of a [graph] defined by taking a [subset] U of [vertices] and taking the [edges] between the [vertices] of U
See also: [subgraph], [graph_minor], [induced_subhypergraph], [induced_cycle]
Up: [graph]
+
+Aliases: induced subgraphs
diff --git a/subgraph b/subgraph
@@ -0,0 +1,7 @@
+# Subgraph
+
+A [graph] obtained from another [graph] by keeping the same [vertices] and a [subset] of the [edges]
+
+Up: [graph]
+
+Aliases: subgraphs
diff --git a/triangle_free_graph b/triangle_free_graph
@@ -7,3 +7,5 @@ They are known to have unbounded [chromatic_number]
[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
