# Projective graphs

Let the category $$\mathbf{Gr}$$ consist of simple, undirected graphs, together with graph homomorphisms. We say that a graph $$P$$ is projective if for all graphs $$A, B$$ with a surjective graph homomorphism $$s:A\to B$$ and every graph homomorphism $$h:P\to B$$ there is a graph homomorphism $$f:P\to A$$ such that $$h = s\circ f.$$

As an example, for $$n>2$$ the complete graph $$K_n$$ is not projective: Let $$B = K_n$$, and let $$A$$ be a graph with $$\chi(A) = n$$ but $$A$$ contains no clique of size $$n$$. Let $$s:A\to B$$ be any coloring, let $$h:K_n \to B$$ be the identity, then there is no $$f: K_n \to A$$ such that $$h=s\circ f$$.

Question. Given an integer $$n>2$$, is there a projective graph $$G$$ with $$\chi(G) =n$$?

Let $$P$$ be any graph with $$\chi(P) = n > 2$$. Let $$B = K_n$$ and let $$A$$ be $$K_{n,n}$$ minus a perfect matching $$M = \{(c_i,d_i): i \in [n]\}$$. A surjective homomorphism $$s : A \to B$$ is given by mapping both $$c_i$$ and $$d_i$$ to vertex $$i$$ of $$B$$. Since $$\chi(P) = n$$, there is some homomorphism $$h : P \to B$$. But of course there is no homomorphism from $$P$$ to $$A$$ since $$\chi(A) = 2 < \chi(P)$$.
Even if you only consider pairs $$A,B$$ where $$P$$ has a homomorphism to $$A$$, it still is not true. You can let $$B = K_{2n}$$ and let $$A$$ be the disjoint union of $$K_{2n,2n}$$ minus a perfect matching and $$K_n$$. Define $$s : A \to B$$ such that the restriction to the $$K_{2n,2n}$$ minus a perfect matching is as above, and suppose it maps the $$K_n$$ to the first $$n$$ vertices of $$B$$. Now let $$h$$ be a homomorphism that maps $$P$$ to the last $$n$$ vertices of $$B$$. Any homomorphism from $$P$$ to $$A$$ must map all of $$P$$ to the $$K_n$$ part of $$A$$, and then composing this with $$s$$ maps $$P$$ to the first $$n$$ vertices of $$B$$, and so this composition cannot be equal to $$h$$.