Ten Graph Parameters
No public endorsements yet.
Loading review…
Sign in with ORCIDAbstract
This draft extends an overview and hierarchy of graph parameters by defining ten further parameters:
- Boxicity
- c-closure
- Chordal intersection dimension
- Cochromatic number
- Distance to block graphs
- Distance to chordal graphs
- Distance to distance-hereditary graphs
- Distance to interval graphs
- Edge clique cover number
- Vertex integrity
Throughout, graphs are finite, simple, and undirected, and may be disconnected. All ten parameters assign zero to the empty graph. Boxicity and chordal intersection dimension allow zero dimensions and zero factors, respectively, so complete graphs have value zero. The c-closure convention also assigns zero to complete graphs.
The draft also defines the underlying structures and graph classes in separate concepts:
- Edge clique covers
- Cochromatic partitions
- Box representations
- Interval representations
- Chordal intersection representations
- c-closed graphs
- Chordal graphs
- Block graphs
- Distance-hereditary graphs
- Interval graphs
Concepts
- def
BlockGraphs - def
Boxicity - def
BoxRepresentation - def
CClosedGraphs - def
ChordalGraphs - def
ChordalIntersectionDimension - def
ChordalIntersectionRepresentation - def
Closure - def
CochromaticNumber - def
CochromaticPartition - def
DistanceHereditaryGraphs - def
DistanceToBlock - def
DistanceToChordal - def
DistanceToDistanceHereditary - def
DistanceToInterval - def
EdgeCliqueCover - def
EdgeCliqueCovering - def
IntervalGraphs - def
IntervalRepresentation - def
VertexIntegrity
Concept map
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-560391,
author = {Hendrik Molter and Codex (GPT-6)},
title = {Ten Graph Parameters},
year = {2026},
howpublished = {Lax Archive, lax-560391},
url = {https://laxarchive.org/lax-560391/},
note = {draft},
}
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments