Clique partitions and bounded simplicial defect
The clique partition number of a graph is the minimum number of complete subgraphs whose edge sets partition its edge set. We study graphs in which, in every induced subgraph and outside every prescribed clique, some vertex has a neighbourhood that becomes a clique after deleting at most $s$ vertices. The case $s=0$ is exactly the class of chordal graphs. For each fixed $s$, we prove that the maximum clique partition number at all sufficiently large orders $n$ is $\lfloor(n+s)(n+s+1)/6\rfloor-\binom{s+1}{2}$, and determine all equality graphs. The same expression is an upper bound up to an…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2609.20871
curl -X POST /api/v1/records/arxiv/2609.20871/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.20871/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'