# Polynomial time construction of families of pairwise nonhomomorphic graphs

Is it true that for all $n$ there are $n$ pairwise nonhomomorphic graphs with $poly(n)$ vertices?

Is there a polynomial time algorithm for constructing such families of graphs?

• This is not a research-level question, but rather a fairly easy homework exercise. (Yes and yes.) – Jeffε Dec 2 '13 at 20:46
• I also thought this should be an easy question. I have asked a graph theorist and he said he didn't know the answer. The most relevant paper I have found so far is the iterative product of Peterson graph. – Anonymous Dec 2 '13 at 22:12
• @JɛﬀE: It is possible that I am not looking at the problem in the right way. Can you give some idea about the construction? Pairwise nonhomomorphic means there shouldn't be any homomorphism from any graph in the family to any other graph in the family. – Anonymous Dec 2 '13 at 22:23
• Note that if there is a homomorphism from $G$ to $H$ then $\omega(G) \leq \omega(H)$ and $\chi(G) \leq \chi(H)$. To answer your question, it suffices to construct a family of graphs $G_1$, ..., $G_n$ with $\omega(G_1) < \dots < \omega(G_n)$ and $\chi(G_1) > \dots > \omega(G_n)$. For instance, let $A_k$ be a graph with a “small” clique number and chromatic number $k$ (e.g. a random $G(n, p)$ graph); let $K_k$ be the complete graph on $k$ vertices. Let $G_i$ be the union of $K_{n+i}$ and $A_{3n-i}$ for $i\in\{1,\dots, n\}$. – Yury Dec 4 '13 at 16:03
• @Yury: Is there an explicit nonprobabilistic construction? Is there a deterministic polytime algorithm for constructing a graph with clique number $w$ and and chromatic number $k$? – Anonymous Dec 5 '13 at 15:37

## 2 Answers

Take cycles $C_{p_1}, \ldots, C_{p_n}$ where $p_i$ is the $i$th prime number.

We can find the first $n$ prime number in time polynomial in $n$.

• The solution is due to Guowei (David) Lu (an undergraduate student in UofT). – Kaveh Dec 11 '13 at 20:47

The problem without a size bound and also in the infinite case was studied in 1960s by Pavol Hell and his colleagues. They called them mutually rigid graphs.

Similar constructions work for the finite case. For directed case this is quite easy, take paths of length $n+5$ with the following pattern:

$$\overset{2+k\text{ times}}{\overbrace{\rightarrow\ldots\rightarrow}} \leftarrow\overset{n+2-k\text{ times}}{\overbrace{\rightarrow\ldots\rightarrow}}$$

To get an undirected graph one can replace the directed edges with a strongly rigid graph that mimics the homomorphism actions of a directed edge. See figure 4.9 in section 4.4 the replacement operation (pages 117-122) in