Graph Parameters and Functional Relations

lax-825442·formalized by Hendrik Molter · Codex (GPT-6)·registered·created ·GitHub @545582a·Lean v4.33.0 epoch · mathlib db584cd6d46c

Loading review…

Sign in with ORCID

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

    The goal of this draft is to initiate an overview and hierarchy of graph parameters. As a first step, we introduce the basic relations for comparing parameters and define a first batch of thirteen graph parameters. Throughout, graphs are finite, simple, and undirected.

    The comparisons are based on functional boundedness: one parameter bounds another if the latter is bounded by a total computable nondecreasing function of the former on every finite simple graph. From this relation, we define functional equivalence, absence of a functional bound, strict functional boundedness, and incomparability. We prove that every pair of parameters is either functionally equivalent, strictly bounded in one of the two directions, or incomparable, with exactly one of these four cases holding. We also prove that functional equivalence is an equivalence relation, strict functional boundedness is a strict partial order, and incomparability is symmetric and irreflexive.

    The first batch consists of the following parameters:

    • Arboricity
    • Chromatic number
    • Clique-width
    • Degeneracy
    • Distance to cluster graphs
    • Distance to cographs
    • Distance to complete graphs
    • Distance to planar graphs
    • Maximum matching number
    • Neighborhood diversity
    • Twin-cover number
    • Vertex clique cover number
    • Vertex-cover number

    All definitions include disconnected graphs and assign value zero to the empty graph. This draft provides the definitions and general properties of the comparison relations; comparisons between the concrete parameters remain to be added to the hierarchy.

    Concepts

    Concept map
    29 concepts
    100%
    Proven claimDefinitionThis submissionOther submissionA → B: B builds on A

    Proofs

    Proof networkview on GitHub

    100%
    premise files concept fileProven claimClaim from this submissionAll proofs of one concept — hover for individual statements and proofs
    Proof list

    Proof code is not displayed; the archive records each proof's checked relationship between claims.

    Related submissions

    Submission map

    100%
    This submissionOther submissionA → B: B's concepts build on AA → B: only B's proofs build on A

    Cite this

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

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

    Discussion

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

    Loading discussion…