Graph Parameters and Functional Relations
No public endorsements yet.
Loading review…
Sign in with ORCIDAbstract
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
- thm✓
EquivalentEquivalence - thm✓
IncomparableProperties - thm✓
RelationClassification - thm✓
StrictlyBoundsOrder
- def
Arboricity - def
Bounds - def
ChromaticNumber - def
CliqueWidth - def
Degeneracy - def
DistanceToClique - def
DistanceToCluster - def
DistanceToCograph - def
DistanceToPlanar - def
DoesNotBound - def
Equivalent - def
Incomparable - def
MaximumMatching - def
NeighborhoodDiversity - def
StrictlyBounds - def
TwinCover - def
VertexCliqueCover - def
VertexCover
Concept map
Proofs
Proof networkview on GitHub
Proof list
-
⊢
Lax825442Proofs.EquivalentEquivalence.equivalent_equivalence -
⊢
Lax825442Proofs.IncomparableProperties.incomparable_symmetric_irreflexive -
⊢
Lax825442Proofs.RelationClassification.relationClassification -
⊢
Lax825442Proofs.StrictlyBoundsOrder.strictlyBounds_strictOrder
Lean sources for these proofs: proofs/ on GitHub
Proof code is not displayed; the archive records each proof's checked relationship between claims.
Related submissions
Submission map
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.
0 comments