# If a graph G is the union of $n$ cliques of size $n$ no two of which share more than one vertex, then $\chi_f(G)=n$. $\omega(G)=n$

Theorem: If a graph G is the union of $n$ cliques of size $n$ no two of which share more than one vertex, then $\chi_f(G)=n$. Prove that $\omega(G)=n$.

A clique is a subset of vertices of an undirected graph such that its induced subgraph is complete (every two distinct vertices in the clique are adjacent).

The clique number $\omega(G)$ of a graph $G$ is defined as the maximum size of a subset of $V(G)$ such that the subset induces a complete graph (a graph where each two vertices are adjacent) in $G$.

As noted in the comment below, this answer assumes that the cliques are connected by a common edge, rather than by a common vertex as indicated in the question.

Clearly, we have $\omega(G) \geq n$. For any graph, we have $\omega \leq \chi_f \leq \chi$. It therefore suffices, for the purposes of this proof, to show that $\chi(G) \leq n$. That is, it suffices to demonstrate that $G$ has a valid (vertex) coloring on $n$ colors.

Let $C_1,\dots,C_n$ denote the cliques (i.e. the sets of vertices from the cliques) that form the graph. For each pair $i \neq j$ with $1 \leq i,j \leq n$, let $v_{i,j}$ denote the vertex in $C_i$ such that $v_{i,j} \sim w$ for some $w \in C_j$. Note the following:,

• If such a vertex exists, there is at most one such $v_{i,j}$ per pair $i \neq j$.
• For every $j,k$, we have $v_{i,j} \sim v_{i,k}$ since both vertices are elements of the clique $C_i$.
• In each clique $C_i$, there are at most $n-1$ vertices $v_{i,j}$ (for some $j$). That is, there is at least one vertex $v$ such that $v$ is only adjacent to other vertices in $C_i$.

Let $B = \{v_{i,j} : i,j = 1,\dots,n\}$. Consider the induced subgraph on the vertices of $B$. By the last note, this graph has degree at most $n - 1$. Thus, with a greedy coloring, we see that $B$ has a valid coloring on $n$ colors.

Now, consider an arbitrary $C_i$. With the coloring on $B$, we have assigned distinct colors to any pair $v_{i,j}$. This coloring on $C_i$ may be extended to a coloring of the entire clique. Note that any newly colored vertices are adjacent only to other elements of the clique. Thus, we have extended the coloring on $B$ to a valid coloring on $B \cup C_i$.

Doing this for all $C_i$, we have an $n$-coloring for the entirety of the graph $G$.

• There might be a nice trick here if we instead use an $n$-fold coloring on $n^2$ colors to show that $\chi_f \leq n$, but I wasn't able to see it. Mar 5 '17 at 20:29
• Isn't the main theorem the Erdős–Faber–Lovász conjecture? en.wikipedia.org/wiki/… Oct 21 '17 at 10:21
• @C.F.G That's troubling... I'm not quite sure where my mistake is, though. Oct 21 '17 at 14:06
• Your argument works if the cliques are made connected by edges; instead, they share vertices. There is a vertex $v_{i,j}$ contained in both $C_i$ and $C_j$; it is adjacent (or equal) to $v_{i,k}$ and $v_{k,j}$ for $k \ne i,j$, so it can have degree (in $B$) of up to $2(n-2)$. Oct 21 '17 at 15:34
• @MishaLavrov Ah, I should have been more careful. Thank you. Oct 21 '17 at 19:58