Lax Lean Archive

While this submission is a draft, it cannot be used by other submissions.

Five Graph Width Parameters

lax-183560·formalized by Hendrik Molter · Codex (GPT-6)·created ·GitHub @fe4b2de·Lean v4.33.0 epoch · mathlib db584cd6d46c

Loading review…

Community review

Flags

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

No flags have been submitted.

    Community review

    Flag this submission

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

    Abstract

    This draft extends an overview and hierarchy of graph parameters by defining five width parameters:

    • treedepth;
    • pathwidth;
    • branchwidth;
    • rank-width;
    • modular-width.

    Throughout, graphs are finite, simple, and undirected, and may be disconnected. All five parameters assign zero to the empty graph. Treedepth counts vertices in the height of a rooted forest. Branchwidth is zero for graphs with at most one edge, and modular-width is zero for cographs.

    The draft also defines the underlying structures:

    • rooted forests;
    • path decompositions;
    • branch decompositions;
    • cut-rank;
    • modular decompositions.

    Concepts

    Concept map
    10 concepts
    100%
    DefinitionThis submissionA → B: B builds on A

    Proofs

    No proofs in this submission.

    Related submissions

    No other submission in the archive builds on this one, and this one builds on none.

    Cite this

    This is only the formalizers. The authors of the formalized results may be different (see References).

    @misc{lax-183560,
  author = {Hendrik Molter and Codex (GPT-6)},
  title = {Five Graph Width Parameters},
  year = {2026},
  howpublished = {Lax Archive, lax-183560},
  url = {https://laxarchive.org/lax-183560/},
  note = {draft},
}

    Discussion

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

    Loading discussion…