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$?
 A: No.
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$.
