Let the category $\mathbf{Gr}$ consist of simple, undirected graphs, together with [graph homomorphisms](https://en.wikipedia.org/wiki/Graph_homomorphism). 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$?



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


