commit 4a2cd9ce25b8ec8b865dcc5f22f9b2d6d6bb5f01
parent d3bcb5e3ca1bd8beab6c03ed99337eda63cae1fe
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Wed, 8 Jan 2025 13:37:12 +0100
commit with codex
Diffstat:
12 files changed, 68 insertions(+), 7 deletions(-)
diff --git a/adjacency_matrix b/adjacency_matrix
@@ -11,4 +11,4 @@ Up: [graph_representation]
Aliases: adjacency matrices
-See also: [adjacency_list]
+See also: [adjacency_list], [adjacent]
diff --git a/cograph b/cograph
@@ -2,6 +2,10 @@
https://en.wikipedia.org/wiki/Cograph
-The class of cographs is the class of [graph] defined by starting from the single vertex graph and closing by the [complementation] and [disjoint_union] operations
+The [graph_class] of *cographs* is the [graph_class] of [undirected_graphs] defined by starting from the [single_vertex_graph] and [graph_closing] by the [graph_complementation] and [graph_disjoint_union] [graph_operations].
+
+Also called the P4-free graphs, cf [pk_free_graph].
Up: [graph_family]
+
+Aliases: cographs
diff --git a/even_hole_free_graph b/even_hole_free_graph
@@ -2,7 +2,7 @@
https://en.wikipedia.org/wiki/Even-hole-free_graph
-A [graph_undirected] without [hole] of [even] length
+An [undirected_graph] without [hole] of [even] length
[survey_paper]: [vuskovic2010even]
@@ -10,4 +10,4 @@ It is an [open_problem] whether [graph_coloring] or [maximum_independent_set] co
Up: [undirected_graph], [hole], [graph_tractability]
-See also: [graph_perfect], [even_cycle_free_graph]
+See also: [graph_perfect], [even_cycle_free_graph], [graph_h_free]
diff --git a/graph_h_free b/graph_h_free
@@ -0,0 +1,9 @@
+# H-free graph
+
+An [undirected_graph] is *H-free* if it does not have an [undirected_graph] H as an [induced_minor]
+
+Each [undirected_graph] H thus defines a [graph_family]
+
+- [graph_pk_free]
+
+Up: [graph_family]
diff --git a/graph_h_minor_free b/graph_h_minor_free
@@ -0,0 +1,11 @@
+# H-minor-free graph
+
+An [undirected_graph] is *H-minor-free* if it does not have an [undirected_graph] H as a [graph_minor]
+
+Each [undirected_graph] H thus defines a [graph_family], which must be [sparse_graphs]
+
+discussed in https://en.wikipedia.org/wiki/Graph_minor
+
+Up: [graph_family]
+
+See also: [graph_h_free]
diff --git a/graph_isomorphism b/graph_isomorphism
@@ -5,3 +5,5 @@
Up: [isomorphism] of [graph]
See also: [graph_homomorphism], [canonical_labeling], [weisfeiler_leman], [graph_automorphism]
+
+Aliases: graph isomorphic
diff --git a/graph_minor b/graph_minor
@@ -6,6 +6,6 @@
Up: [graph]
-See also: [robertson_seymour], [topological_minor], [excluded_minor]
+See also: [robertson_seymour], [topological_minor], [excluded_minor], [forbidden_minor], [induced_minor]
Aliases: graph minors
diff --git a/graph_p5_free b/graph_p5_free
@@ -0,0 +1,7 @@
+# Graph p5 free
+
+https://www.graphclasses.org/classes/gc_396.html
+
+cf, e.g., [chudnowski2023cops]
+
+Up: [graph_pk_free]
diff --git a/graph_pk_free b/graph_pk_free
@@ -0,0 +1,15 @@
+# P_k-free graph
+
+An [undirected_graph] is *P_k-free* if it does not have an [induced_subgraph] which is [graph_isomorphic] to a [path] on k [vertices]
+
+- P_2-free means no [edge] at all, so [graph_empty], or [independent_set]
+- P_3-free means every [connected_component] is a [clique]
+ - https://math.stackexchange.com/questions/3564039/describe-all-graphs-that-do-not-contain-p-3-as-an-induced-subgraph
+- P_4-free are precisely the [cographs]
+- P_5-free: [graph_p5_free]
+
+Up: [graph_family], [graph_h_free]
+
+Aliases: PK free graph
+
+See also: [forbidden_minor]
diff --git a/graph_sparse b/graph_sparse
@@ -0,0 +1,9 @@
+# Graph sparse
+
+https://en.wikipedia.org/wiki/Dense_graph
+
+An [undirected_graph] where the number of [edges] is o(n^2), for n the number of [vertices]
+
+Up: [graph_family]
+
+Aliases: sparse graph, sparse graphs
diff --git a/independent_set b/independent_set
@@ -1,6 +1,8 @@
# Independent set
-An independent set is a subset of vertices such that no two vertices of the subset are adjacent
+https://en.wikipedia.org/wiki/Independent_set_%28graph_theory%29
+
+An *independent set* is a [subset] of [vertices] of an [undirected_graph] such that no two [vertices] of the [subset] are [adjacent]. Also called a "coclique" or "anticlique".
## Connections
@@ -30,3 +32,5 @@ By [duality], counting independent sets exactly is the same as counting [vertex_
See also: [matching], [vertex_cover]
Up: [graph_substructure]
+
+Aliases: coclique, anticlique
diff --git a/triangle_free_graph b/triangle_free_graph
@@ -6,4 +6,4 @@ They are known to have unbounded [chromatic_number]
[computational_problem] of recognizing them: see [triangle_detection]
-Up: [triangle], [graph]
+Up: [triangle], [graph], [graph_h_free]
