Edge clique covers of graphs with independence number two: does ecc(G) ≤ n always hold?

For a simple graph $G$ on $n$ vertices, the edge clique cover number $ecc(G)$ is the minimum number of cliques whose union contains all edges of $G$; equivalently the intersection number of $G$. Chen, Jacobson, Kézdy, Lehel, Scheinerman and Wang conjectured in 2000 that every claw-free graph satisfies $ecc(G)\le n$, and Javadi and Hajebi proved this in 2018 for all claw-free graphs with independence number $\alpha(G)\ge 3$, leaving open exactly the case $\alpha(G)=2$ (equivalently, complements of triangle-free graphs, which are automatically claw-free). The surviving conjecture is: every simple graph $G$ with $\alpha(G)=2$ satisfies $ecc(G)\le n$; the bound is tight already at $n=5$ ($C_5$). The best general bounds are $\min\{n+\delta(G),\ 2n-\Omega(\sqrt{n\log n})\}$, and the conjecture is known for graphs with no dominating edge, for diameter-3 graphs, for graphs omitting any fixed 4-vertex induced subgraph $H$ with $\alpha(H)\le 2$, and (Ramamonjisoa 2021) for graphs having a dominating edge $uv$ with $G\setminus\{u,v\}$ of diameter 3, which reduces the problem to connected diameter-2 graphs in which deleting the endpoints of any dominating edge leaves diameter 2. The conjecture remains open.

Background

For a finite simple graph $G$ on $n$ vertices, a clique is a set of vertices any two of which are adjacent, and an edge clique cover is a collection of cliques whose union contains every edge of $G$; the minimum size of such a collection is the edge clique cover number $ecc(G)$. Equivalently (Erdős, Goodman and Pósa, 1966), $ecc(G)$ is the intersection number of $G$: the smallest size of a ground set on which the vertices of $G$ can be represented by subsets so that two subsets intersect exactly when the corresponding vertices are adjacent. In general the parameter can be quadratic in $n$ — a complete bipartite graph $K_{n/2,n/2}$ is triangle-free, so each of its $n^2/4$ edges requires its own clique — which motivates finding natural classes where a linear (order-$n$) number of cliques suffices.

The independence number $\alpha(G)$ is the size of a largest set of pairwise non-adjacent vertices. A claw is the 4-vertex star $K_{1,3}$, and $G$ is claw-free if it has no induced claw. Since the three leaves of a claw form an independent triple, every graph with $\alpha(G)\le 2$ is claw-free; graphs with $\alpha(G)=2$ are exactly the complements of triangle-free graphs. This is the classical setting of the question: Chen, Jacobson, Kézdy, Lehel, Scheinerman and Wang (2000), after proving the case of locally cobipartite (quasi-line) graphs — graphs in which the neighborhood of every vertex can be partitioned into two cliques — asked the following.

Problem (Chen et al., 2000). If $G$ is claw-free, is $ecc(G)\le n$?

Javadi and Hajebi (2018) answered affirmatively for all connected claw-free graphs with $\alpha(G)\ge 3$, and characterized the equality cases (the icosahedron graph, the complement of a particular 10-vertex graph, and the powers $C_n^p$ of the cycle for $1\le p\le\lfloor(n-1)/3\rfloor$). Their proof rests on the Chudnovsky–Seymour structure theorem for claw-free graphs, a decomposition theorem available only when $\alpha(G)\ge 3$. The case $\alpha(G)=1$ is trivial ($G$ is complete and $ecc(G)=1$), so the conjecture of Chen et al. survives in exactly one case, stated as a conjecture in its own right by Charbit, Hahn, Kamiński, Lafond, Lichiardopol, Naserasr, Seamone and Sherkati (2021) and again by Ramamonjisoa (2021):

Conjecture. If $G$ is a simple graph with $\alpha(G)=2$, then $ecc(G)\le n$.

The bound would be tight: the 5-cycle $C_5$ has $\alpha(C_5)=2$ and $ecc(C_5)=5$.

Graphs with $\alpha(G)=2$ have a rigid local structure that drives every known approach. For any vertex $x$, its non-neighborhood $\overline{N[x]}$ (the set of vertices not adjacent to $x$) is a clique, since two non-adjacent non-neighbors of $x$ together with $x$ would form an independent triple. Hence the family $\{\overline{N[x]}:x\in V(G)\}$ of at most $n$ cliques is a canonical cover — but it covers no dominating edge: an edge $uv$ is a dominating edge if every other vertex is adjacent to $u$ or to $v$, and a dominating edge lies in no non-neighborhood clique. The entire difficulty of the conjecture is concentrated in covering dominating edges.

The verified cases and best bounds are as follows. If $G$ has no dominating edge, the canonical cover gives $ecc(G)\le n$. Graphs with $\alpha(G)=2$ have diameter (maximum graph distance between two vertices) at most 3, and if the diameter is 3 then $ecc(G)\le\lceil n/2\rceil+1$. Charbit et al. (2021) proved the first linear bounds in general, $ecc(G)\le\min\{n+\delta(G),\ 2n-\Omega(\sqrt{n\log n})\}$ where $\delta(G)$ is the minimum degree, and improved both to $3n/2$ for the fractional edge clique cover (the linear-programming relaxation in which cliques carry nonnegative weights and every edge must receive total weight at least 1). They also verified the conjecture when $G$ omits any fixed 4-vertex graph $H$ with $\alpha(H)\le 2$ as an induced subgraph (this covers the $2K_2$-free and co-claw-free cases) and when the edge packing number with respect to cliques — the maximum number of edges of $G$, no two of which lie together in a common clique, a lower bound for $ecc(G)$ — equals $n$. The $\sqrt{n\log n}$ term in the second bound comes from the independence bound for triangle-free graphs via the Ramsey number $R(3,t)$, which is tight for that method, so approaching $n$ requires a different covering strategy.

Ramamonjisoa (2021) contributes two further reductions. Theorem 4: if $G$ has $\alpha(G)=2$ and a dominating edge $uv$ such that $G\setminus\{u,v\}$ has diameter 3, then $ecc(G)\le n$. Combined with the earlier cases, it suffices to prove the conjecture for connected graphs with $\alpha(G)=2$ and diameter 2 in which, for every dominating edge $uv$, the graph $G\setminus\{u,v\}$ still has diameter 2 — the residual regime. Theorem 8 bounds, without settling, another large class: a path $x_0x_1x_2x_3x_4$ is a double top if its edges are dominating and $x_2$ is adjacent to neither $x_0$ nor $x_4$; it is incompatible if $x_1x_3$ is not an edge; a supercycle is a cycle of at least four dominating edges in which any two vertices at distance 2 along the cycle are adjacent. If $G$ with $\alpha(G)=2$ contains neither supercycles nor incompatible double tops, then $ecc(G)\le\tfrac32 n$ (refined to $n+f/2$, where $f$ counts the vertices incident to edges left uncovered by the canonical extended cliques). The paper emphasizes that forbidding incompatible double tops is essential to its construction — they are precisely the obstruction to extending the cliques $\overline{N[x]}$ simultaneously along several dominating edges — and proposes, as a research program, a covering theory of maximal cliques that would build $n$ maximal cliques attaining or approaching the bound $n$.

Two neighboring facts delineate the conjecture's boundary. First, one level up in $\alpha$, linear behavior already fails: Nguyen, Scott, Seymour and Thomassé (2024) showed that graphs with no stable set of size four — that is, $\alpha\le 3$ — may require more than linearly many cliques to cover their edges (and graphs with no induced $K_{t,t}$ need at most $O(n^{2-1/(2t)})$). Their graphs may contain claws, so this does not contradict the claw-free conjecture, but it shows that $\alpha=2$ is the last frontier on which a linear bound is even plausible. Second, many $\alpha=2$ graphs are far from extremal: the complements of paths and cycles have $\alpha=2$, yet their edge clique cover number is only $\log_2 n+\Theta(\log_2\log_2 n)$ — a 1985 conjecture of de Caen, Gregory and Pullman recently settled by Ning (2026) through Kohayakawa's conjecture on long induced paths in Kneser graphs (the Kneser graph $KG(n,k)$ has the $k$-subsets of an $n$-set as vertices, adjacent when disjoint). The conjecture is thus a genuinely worst-case statement about the hardest configurations of dominating edges in diameter-2 graphs.

Problem Statement

Prove or disprove: every simple graph $G$ on $n$ vertices with independence number $\alpha(G)=2$ admits an edge clique cover of at most $n$ cliques; that is, $ecc(G)\le n$. Equivalently: does every complement of a triangle-free graph admit an intersection representation over a ground set of at most $n$ elements, that is, an assignment of a subset of the ground set to each vertex such that two vertices are adjacent exactly when their subsets intersect?

By the published reductions, an affirmative answer suffices for the residual class: connected graphs with $\alpha(G)=2$ and diameter 2 in which, for every dominating edge $uv$, the graph $G\setminus\{u,v\}$ also has diameter 2 — every other case is settled (graphs with no dominating edge; diameter 3; $G\setminus\{u,v\}$ a clique or disconnected for a dominating edge $uv$; all fixed 4-vertex forbidden-induced-subgraph classes $H$ with $\alpha(H)\le 2$). The bound $n$ is best possible in general, as shown by $C_5$ (where $\alpha=2$ and $ecc=5$).

The conjecture is a universal statement over all graphs with $\alpha(G)=2$: covering all of them settles it, either directly or via the residual class together with the published cases it may cite, while a single finite graph with $\alpha(G)=2$ and $ecc(G)>n$ refutes it. Strengthenings suggested by Ramamonjisoa (2021) — for example that two dominating edges $uv,xy$ with $G\setminus\{u,v,x,y\}$ of diameter 3 should already force $ecc(G)\le n$, or a covering theory of maximal cliques attaining the bound $n$ — are natural follow-up directions outside the scope of the conjecture.

References

1. Pierre Charbit, Geňa Hahn, Marcin Kamiński, Manuel Lafond, Nicolas Lichiardopol, Reza Naserasr, Ben Seamone, Rezvan Sherkati. Edge clique covers in graphs with independence number two. Journal of Graph Theory 97 (2021) 324–339. doi:10.1002/jgt.22657, https://doi.org/10.1002/jgt.22657 (full text also available via HAL preprint hal-02969899)
2. Frank Ramamonjisoa. Edge Clique Covers in Graphs with Independence Number Two: a Special Case. arXiv:2112.03961 [math.CO], 2021. doi:10.48550/arXiv.2112.03961, https://arxiv.org/abs/2112.03961
3. Guantao Chen, Michael S. Jacobson, André E. Kézdy, Jenö Lehel, Edward R. Scheinerman, Chi Wang. Clique covering the edges of a locally cobipartite graph. Discrete Mathematics 219 (2000) 17–26. doi:10.1016/S0012-365X(99)00333-7, https://doi.org/10.1016/S0012-365X(99)00333-7
4. Ramin Javadi, Sepehr Hajebi. Edge clique cover of claw-free graphs. Journal of Graph Theory 90 (2018) 311–405. doi:10.1002/jgt.22403, https://arxiv.org/abs/1608.07723 (arXiv:1608.07723)
5. Ramin Javadi, Zeinab Maleki, Behnaz Omoomi. Local Clique Covering of Claw-Free Graphs. Journal of Graph Theory 81 (2016) 92–104. doi:10.1002/jgt.21864, https://doi.org/10.1002/jgt.21864
6. Paul Erdős, A. W. Goodman, Louis Pósa. The Representation of a Graph by Set Intersections. Canadian Journal of Mathematics 18 (1966) 106–112. doi:10.4153/cjm-1966-014-3, https://doi.org/10.4153/cjm-1966-014-3
7. Maria Chudnovsky, Paul Seymour. The structure of claw-free graphs. In: Surveys in Combinatorics 2005, London Mathematical Society Lecture Note Series 327, Cambridge University Press, 2005, pp. 153–172. doi:10.1017/CBO9780511734885.008, https://doi.org/10.1017/CBO9780511734885.008
8. Tung Nguyen, Alex Scott, Paul Seymour, Stéphan Thomassé. Clique covers of H-free graphs. European Journal of Combinatorics 118 (2024) 103909. doi:10.1016/j.ejc.2023.103909, https://arxiv.org/abs/2211.12065 (arXiv:2211.12065)
9. Bo Ning. Kohayakawa's conjecture and clique coverings of complements of paths and cycles. arXiv:2608.11132 [math.CO], 2026. doi:10.48550/arXiv.2608.11132, https://arxiv.org/abs/2608.11132
10. de Caen, Gregory, Pullman. Clique Coverings of Complements of Paths and Cycles. In: Cycles in Graphs, Annals of Discrete Mathematics 27, North-Holland, 1985, pp. 257–267. doi:10.1016/S0304-0208(08)73020-2, https://doi.org/10.1016/S0304-0208(08)73020-2
11. 黄悦雯 (Huang Yuewen). Edge Clique Cover Number of Graphs with Independence Number Two (关于独立数为2的图的边团覆盖数). Advances in Applied Mathematics (Hans Publishers) 15 (2026) 119–124. doi:10.12677/aam.2026.152054, https://doi.org/10.12677/aam.2026.152054
12. Fedor V. Fomin, Petr A. Golovach, Danil Sagunov, Kirill Simonov. Edge Clique Partition and Cover Beyond Independence. arXiv:2506.21216 [cs.DS], 2025. doi:10.48550/arXiv.2506.21216, https://arxiv.org/abs/2506.21216 (extended abstract in the proceedings of ESA 2025)
13. Csilla Bujtás, Akbar Davoodi, Ervin Győri, Zsolt Tuza. Clique coverings and claw-free graphs. European Journal of Combinatorics 88 (2020) 103114. doi:10.1016/j.ejc.2020.103114, https://arxiv.org/abs/1608.07686 (arXiv:1608.07686)
14. Stephan Schwartz. An overview of graph covering and partitioning. Discrete Mathematics 345 (2022) 112884. doi:10.1016/j.disc.2022.112884, https://doi.org/10.1016/j.disc.2022.112884