Given an infinite graph $G$, with clique number $2< \omega (G) < \infty$, is it possible to remove vertices such that the remaining subgraph has clique number $\omega (G)-1$, under the restriction that you cannot remove a clique of size $\omega (G)$?

  • $\begingroup$ I'm specifying an infinite graph because it would prove it in the finite case as well. I guess it is just more general, but yes I am assuming $\omega (G)$ is finite. $\endgroup$ – mow Mar 23 '15 at 11:29
  • $\begingroup$ Does the restriction "you cannot remove a clique of size $\omega(G)$" simply mean that the induced subgraph of $G$ on the set of removed vertices does not contain a clique of size $\omega(G)$? $\endgroup$ – bof Mar 25 '15 at 20:06

First, let me restate the question:

Let $2\lt k\lt\infty.$ Given a (finite) graph $G=(V,E)$ with clique number $\omega(G)=k,$ can we find a vertex partition $V=V_1\cup V_2$ such that the induced subgraphs $G[V_1]$ and $G[V_2]$ both have clique number less than $k$?

(There is no loss of generality in restricting our attention to finite graphs, because, by a slight generalization of the De Bruijn–Erdős theorem, an infinite graph $G$ will admit such a partition if each of its finite subgraphs does. This can be proved by the usual "compactness argument" using an ultrafilter or the Tychonoff product theorem or the compactness theorem of first-order logic.)

For $k=2$ the answer would be negative, as shown by the example $G=C_5.$ In fact, the answer is negative for all values of $k,$ but the counterexamples for $k\gt2$ are not so simple. I will use the following result of Jon Folkman [Graphs with monochromatic complete subgraphs in every edge coloring, SIAM J. Appl. Math. 18 (1970), 19-24 ] which was later generalized by the Nešetřil–Rödl theorem:

Folkman's Theorem. For each positive integer $k$ there is a graph $G_k$, with clique number $\omega(G_k)=k$, such that every coloring of the edges of $G_k$ with two colors contains a monochromatic $K_k$.

Suppose $k\gt2.$ Consider Folkman's graph $G_k=G=(V,E),$ and consider any partition of the vertex-set $V$ into two disjoint subsets $V_1,V_2.$ Color an edge of $G$ red if it has one endpoint in $V_1$ and the other in $V_2$; otherwise color it blue. Then $G$ contains a monochromatic $K_k$. But a red $K_k$ is impossible for $k\gt2.$ Thus $G$ contains a blue $K_k,$ that is, a $K_k$ whose vertices all lie on the same side of the partition. In other words, either $\omega(G[V_1])=k$ or else $\omega(G[V_2])=k.$

  • $\begingroup$ That was rather elegant. $\endgroup$ – mow Mar 26 '15 at 14:25

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.