Clique-width

Lax825442.CliqueWidth · concepts/Lax825442/CliqueWidth.lean · lax-825442

definition

Loading review…

Sign in with ORCID

Community review

Flags

Each flag is tied to a public ORCID identity and explains why this concept may be incorrect.

No flags have been submitted.

    Community review

    Flag this concept

    State precisely what appears incorrect. This explanation will be public under your ORCID name.

    No source line selected.

    Natural 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
    2 concepts
    100%
    DefinitionThis conceptRelated conceptA → B: B builds on A

    Lean source view on GitHub

    1import Lax271696.CliqueExpr
    2import Mathlib.Combinatorics.SimpleGraph.Maps
    3import Mathlib.Data.Fintype.EquivFin
    4import Mathlib.Order.Lattice.Nat
    5
    6/-!
    7---
    8title: Clique-width
    9type: definition
    10---
    11The clique-width of a graph is the minimum number of labels needed to
    12construct it using vertex creation, disjoint union, the addition of all edges
    13between two distinct label classes, and relabeling.
    14The empty graph has clique-width zero.
    15-/
    16
    17namespace Lax825442.CliqueWidth
    18
    19open Lax271696.CliqueExpr
    20
    21/-- A valid `k`-expression builds a numbered copy of `G`. -/
    22def 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`. -/
    29noncomputable def cliqueWidth {V : Type} [Fintype V] [DecidableEq V]
    30 (G : SimpleGraph V) : ℕ :=
    31 sInf {k | HasCliqueWidthAtMost G k}
    32
    33end Lax825442.CliqueWidth
    34
    35

    Discussion

    Ask a question or add context. Endorsements and structured flags are kept in the review panel above.

    Loading discussion…