The paper studies a question about how efficiently you can cover all the edges of a network using complete subgraphs, where a complete subgraph (or clique) is a set of nodes that are all connected to each other. The goal is to find the minimum number of such cliques needed so that every edge belongs to exactly one clique. This minimum number is called the clique partition number. The authors focus on a broad family of graphs called chordal graphs and their generalizations. Chordal graphs have a special structure: if you look at any cycle of four or more nodes, there is always a shortcut edge cutting across it. A long-standing open question asked by Erdos, Ordman, and Zalcstein was how large the clique partition number can get for chordal graphs on n nodes.
The authors answer this question by proving that for chordal graphs, the clique partition number is at most roughly n squared over 6, up to smaller corrections. They then generalize this to a broader class of graphs where the chordal condition is relaxed by allowing a small number of exceptions, controlled by a parameter s. When s is zero you get ordinary chordal graphs, and as s grows the graphs become less constrained. For each fixed value of s, they identify the exact maximum clique partition number for large enough graphs and even pin down which specific graphs achieve this maximum. This is a precise and complete answer, not just an estimate.
The proof combines two main ingredients. One is a technique called signed fractional localization, which translates the combinatorial problem into a more flexible linear algebraic framework involving weighted or signed versions of clique covers. The other is an explicit construction of edge-disjoint triangles, meaning triangles that share no edges, which provides the extremal examples showing the bounds are tight. The paper also establishes that graphs close to achieving the maximum must structurally resemble the extremal examples, a property called stability. Together, these results give a comprehensive picture of clique partitioning in graphs with bounded structural defect.