If for any graph $H$ we define $\alpha(H)$ to be the cardinality of any maximum size indepedent set in $H$. Then under what conditions can any graph $G$ be expressed as a union of $\alpha(G)$ complete graphs?


Or equivalently if $[S]\_2$ is the set of all two element subsets of $S$, then for which class of graphs $G$ will there exist $\alpha(G)$ sets $V\_{1},V\_2,\ldots V\_{\alpha(G)}$ that satisfy $V(G)=\bigcup\_{n=1}^{\alpha(G)}V\_n$ and $E(G)=\bigcup\_{n=1}^{\alpha(G)}[V\_n]\_2$?


Are there any reasonably simple necessary and sufficient conditions for categorizing these graphs?




---




---


Lastly also note if there are $n$ complete graphs $C\_1,C\_2,\ldots C\_n$ with $G=\bigcup\_{k=1}^n C\_k$ and $n<\alpha(G)$ there must exist an independent set $I$ of $G$ such that $|I|=n+1$ however by assumption we have that $I\subseteq V(G)=\bigcup\_{k=1}^nV(C\_k)$ therefore by the pigeonhole principal there must exists two distinct vertices $u,v\in V(C\_j)$ for some integer $1\leq j\leq n$ yet since $V(C\_j)$ is a clique of $G$ this means we have $\{u,v\}\in E(G)$ contradicting the fact $I$ is an independent set of $G$, which proves $n\geq \alpha(G)$. Thus a a corollary if we let $\theta(G)$ be the [intersection number](https://en.wikipedia.org/wiki/Intersection_number_(graph_theory)) of $G$ then by definition we have that:


$$G\text{ is a union of }\alpha(G)\text{ complete graphs}\iff \alpha(G)=\theta(G)$$


However I'm unable to simplify these equivalent conditions into anything nice either.



When can any graph $G$ be expressed as a union of $\alpha(G)$ complete graphs?
I don't think there is a pretty answer to this question. A graph is in this class iff it is the union of a set of cliques such that each of the cliques has a vertex not in any of the other cliques.


Given a maximum independent set $S$, you can identify said cliques as the closed neighbourhoods of the vertices in $S$. Conversely given such a set of cliques, the special vertices are a maximum independent set.


