Clique partitions and bounded simplicial defect
Abstract
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 ⌊(n+s)(n+s+1)/6⌋−binoms+12, and determine all equality graphs. The same expression is an upper bound up to an additive constant depending only on s at every order. In particular, every chordal graph has clique partition number at most n2/6+n/6+O(1), answering a question of Erdős, Ordman and Zalcstein. We also prove structural stability for sublinear defect and a sharp finite-order theorem for integer signed clique functionals. The proof combines signed fractional localization with an edge-disjoint triangle construction; only a qualitative fractional-packing approximation is required.
Related
- Clique partitions and distinct color sets in list colorings
- Bounded cohomology property on Jacobian elliptic surfaces with simplicial Mori cones
- On partitions with bounded multiplicity restrictions on even parts and with the largest part being odd
- Bounded chromatic number of graphs with small clique number and large minimum degree
- A Bounded-Defect Construction for the Mondrian Art Problem
BibTeX
@misc{okechukwu2026clique,
title = {{Clique partitions and bounded simplicial defect}},
author = {Obinna Okechukwu},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.20871},
eprint = {2609.20871},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.20871},
}
RIS
TY - UNPB
TI - Clique partitions and bounded simplicial defect
AU - Obinna Okechukwu
PY - 2026
DA - 2026/09/15
PB - arXiv
DO - 10.48550/arxiv.2609.20871
UR - https://arxiv.org/abs/2609.20871
AB - 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 ⌊(n+s)(n+s+1)/6⌋−binoms+12, and determine all equality graphs. The same expression is an upper bound up to an additive constant depending only on s at every order. In particular, every chordal graph has clique partition number at most n^2/6+n/6+O(1), answering a question of Erdős, Ordman and Zalcstein. We also prove structural stability for sublinear defect and a sharp finite-order theorem for integer signed clique functionals. The proof combines signed fractional localization with an edge-disjoint triangle construction; only a qualitative fractional-packing approximation is required.
ER -