4
$\begingroup$

Let $\textbf{Grph}$ be the category whose objects are graphs $G = (V,E)$ such that $V$ is a set and $E \subseteq \mathcal{P}_2(V) := \{\{a,b\} \subseteq V: a\neq b\}$. We sometimes write $E(G)$ for $E$. The morphisms are maps $f:G\to H$ such that whenever $\{v,w\}\in E(G)$ then $\{f(v),f(w)\}\in E(H)$.

How can regular epimorphisms in $\textbf{Grph}$ be characterized?

Improve this question
$\endgroup$
5
  • 2
    $\begingroup$ I'm not sure this question is trivial; the category of simple loop-free graphs (or sets equipped with symmetric irreflexive relations) is not a topos or quasi-topos and is not a particularly nice category. $\endgroup$
    – Todd Trimble
    Commented May 12, 2015 at 11:50
  • $\begingroup$ combinatorics.org/ojs/index.php/eljc/article/view/v15i1a1 $\endgroup$
    – Steve Huntsman
    Commented May 12, 2015 at 12:51
  • $\begingroup$ @SteveHuntsman I don't see how the link you posted answers the question; neither of the words "regular" and "epimorphism" appear in the text. $\endgroup$
    – Dominic van der Zypen
    Commented May 12, 2015 at 14:31
  • $\begingroup$ @DominicvanderZypen -- It doesn't answer the question: it merely reinforces Todd's comment and gives context along those lines. $\endgroup$
    – Steve Huntsman
    Commented May 12, 2015 at 14:37
  • $\begingroup$ Sorry for misunderstanding - thanks for clarifying! $\endgroup$
    – Dominic van der Zypen
    Commented May 12, 2015 at 14:39

1 Answer 1

Reset to default
5
$\begingroup$

I think the paper "A canonical factorization for graph homomorphisms", Barry Fawcett, Can J. Math. 29 (4), 1977, 738-743, answers the question.

Theorem 3 states that in $\textbf{Grph}$, strict epimorphisms are the same as extremal epimorphisms, which are the same as "full epimorphisms", meaning morphisms that are surjective on vertices and edges. The paper doesn't mention regular epimorphisms, but $\textbf{Grph}$ has pullbacks, which I think means that strict epimorphisms are the same as regular epimorphisms.

It's not strictly relevant to this question, but I can't resist mentioning this related paper by the same author about epimorphisms in the category of planar graphs, whose main result will bring a smile to the face of any categorically inclined mathematician.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .