Clique-width
Lax825442.CliqueWidth · concepts/Lax825442/CliqueWidth.lean · lax-825442
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Definition
The clique-width of a graph is the minimum number of labels needed to construct it using vertex creation, disjoint union, the addition of all edges between two distinct label classes, and relabeling. The empty graph has clique-width zero.
Concept map
Lean source view on GitHub
| 1 | import Lax271696.CliqueExpr |
| 2 | import Mathlib.Combinatorics.SimpleGraph.Maps |
| 3 | import Mathlib.Data.Fintype.EquivFin |
| 4 | import Mathlib.Order.Lattice.Nat |
| 5 | |
| 6 | /-! |
| 7 | --- |
| 8 | title: Clique-width |
| 9 | type: definition |
| 10 | --- |
| 11 | The clique-width of a graph is the minimum number of labels needed to |
| 12 | construct it using vertex creation, disjoint union, the addition of all edges |
| 13 | between two distinct label classes, and relabeling. |
| 14 | The empty graph has clique-width zero. |
| 15 | -/ |
| 16 | |
| 17 | namespace Lax825442.CliqueWidth |
| 18 | |
| 19 | open Lax271696.CliqueExpr |
| 20 | |
| 21 | /-- A valid `k`-expression builds a numbered copy of `G`. -/ |
| 22 | def HasCliqueWidthAtMost {V : Type} [Fintype V] [DecidableEq V] |
| 23 | (G : SimpleGraph V) (k : ℕ) : Prop := |
| 24 | Fintype.card V = 0 ∨ |
| 25 | ∃ e : Expr (Fintype.card V) k, |
| 26 | ValidFor e (G.comap (Fintype.equivFin V).symm) |
| 27 | |
| 28 | /-- The minimum number of labels in a valid expression for `G`. -/ |
| 29 | noncomputable def cliqueWidth {V : Type} [Fintype V] [DecidableEq V] |
| 30 | (G : SimpleGraph V) : ℕ := |
| 31 | sInf {k | HasCliqueWidthAtMost G k} |
| 32 | |
| 33 | end Lax825442.CliqueWidth |
| 34 | |
| 35 |
Builds on
Used by
none
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments