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$.

  • $\begingroup$ 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. $\endgroup$ Mar 5 '17 at 20:29
  • $\begingroup$ Isn't the main theorem the Erdős–Faber–Lovász conjecture? en.wikipedia.org/wiki/… $\endgroup$
    – C.F.G
    Oct 21 '17 at 10:21
  • $\begingroup$ @C.F.G That's troubling... I'm not quite sure where my mistake is, though. $\endgroup$ Oct 21 '17 at 14:06
  • $\begingroup$ 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)$. $\endgroup$ Oct 21 '17 at 15:34
  • $\begingroup$ @MishaLavrov Ah, I should have been more careful. Thank you. $\endgroup$ Oct 21 '17 at 19:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.