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

<p>We can find the first $n$ prime number in time polynomial in $n$.</p>

CC BY-SA 3.0
2013-12-11T20:47:36.220Z
The solution is due to Guowei (David) Lu (an undergraduate student in UofT).
Kaveh
CC BY-SA 3.0
2013-12-11T20:46:13.747Z
2013-12-11T20:46:13.747Z
Kaveh
<p>The problem without a size bound and also in the infinite case was studied in 1960s by <a href="http://www.cs.sfu.ca/~pavol/" rel="nofollow">Pavol Hell</a> and his colleagues. They called them <em>mutually rigid graphs</em>.</p>

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

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

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

<ul>
<li>Pavol Hell and Jarik Nesetril, <a href="http://ukcatalogue.oup.com/product/9780198528173.do" rel="nofollow">Graphs and Homomorphisms</a>, 2004.</li>
</ul>

CC BY-SA 3.0
2013-12-11T21:08:21.270Z
2013-12-11T21:08:21.270Z
Kaveh
<p>Is it true that for all $n$ 
there are $n$ pairwise nonhomomorphic graphs with $poly(n)$ vertices?</p>

<p>Is there a polynomial time algorithm for constructing such families of graphs?</p>

CC BY-SA 3.0
2013-12-02T20:46:07.093Z
This is not a research-level question, but rather a fairly easy homework exercise.  (Yes and yes.)
Jeffε
CC BY-SA 3.0
2013-12-02T22:12:10.307Z
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
CC BY-SA 3.0
2013-12-02T22:23:01.287Z
@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
CC BY-SA 3.0
2013-12-04T16:03:04.820Z
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
CC BY-SA 3.0
2013-12-05T15:37:08.970Z
@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
<ds.algorithms><graph-theory><co.combinatorics><homomorphism>
Polynomial time construction of families of pairwise nonhomomorphic graphs
Anonymous
# Polynomial time construction of families of pairwise nonhomomorphic graphs

(Asked by: username_0 on 2013-12-02)

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?

**Tags:** ds.algorithms, graph-theory, co.combinatorics, homomorphism

> **Comments:**
> **username_1**: This is not a research-level question, but rather a fairly easy homework exercise.  (Yes and yes.)  
> **username_0**: 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.  
> **username_0**: @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.  
> **username_2**: 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\}$.  
> **username_0**: @username_2: 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$?  

---

## 2 answers

### Answer by username_3 on 2013-12-11. Score: 1 | Accepted answer

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

> **Comments:**
> **username_3**: The solution is due to Guowei (David) Lu (an undergraduate student in UofT).  

---

### Answer by username_3 on 2013-12-11. Score: 0

The problem without a size bound and also in the infinite case was studied in 1960s by [Pavol Hell](http://www.cs.sfu.ca/~pavol/) 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

* Pavol Hell and Jarik Nesetril, [Graphs and Homomorphisms](http://ukcatalogue.oup.com/product/9780198528173.do), 2004.


---

