Monday, 23 April 2012

ct.category theory - Graph properties, categorically defined

There are some subtle point concerning the definition of this category. It has different properties if you define "graph" in a different way.



If you allow your graphs to have loops, then the category of all graph becomes a topological category over SET. In particular all (small) limits and colimits exist in this category. Sometimes it is best to consider only the graphs with loops at all vertices (if you just don't draw them this subcategory can be identified with the category of all simple graphs). The product in this category is the tensor product of graphs. A connected object (in a topological category an object is connected if all morphisms into discrete objects are constant) in this category is exactly a connected graph.



The subcategory of graphs without loops is not that well behaved from the point of view of category theory, But graphs without loops have their merits too: A graph morphism from $(V,E)$ to the complete graph without loops on $n$ vertices is the same thing as a $n$-vertex-coloring of $(V,E)$.

No comments:

Post a Comment