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


1 Answer 1



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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.