As everyone knows :P, a graph is a CW-complex of dimension 1. Knowing that, are there any interesting results in graph theory that arise from working with CW-complexes? And more specifically, in algorithms / computability?
$\begingroup$
$\endgroup$
5
-
$\begingroup$ What kind of results are you thinking about? The question is rather broad. Also, consider adding a major tag (those starting with two letters and a dot). $\endgroup$– Sebastian GoetteCommented Nov 9, 2015 at 19:07
-
$\begingroup$ I imagine something as "Hey, I'd like to know whether this graph has this X propery....wait! Seeing it as a CW-complex, it's much easier!" $\endgroup$– Guillermo MosseCommented Nov 9, 2015 at 19:21
-
$\begingroup$ So I guess things like the hom-complexes used to study colorability are not what you are interested in? You only want to consider the graphs themselves as topological spaces? $\endgroup$– PatrikCommented Nov 9, 2015 at 19:27
-
$\begingroup$ That sounds like something I'd be interested to read about, thanks. Are you talking about this? (link) ? Do you have any paper for me? Anyway, although what you say seems cool, yeah, my main interest is to see the graph as a complex and see what I can obtain from that $\endgroup$– Guillermo MosseCommented Nov 9, 2015 at 19:33
-
$\begingroup$ Configuration spaces in graphs are related to motion-planning problems and they are natural CW-complexes associated to graphs. $\endgroup$– Ryan BudneyCommented Nov 9, 2015 at 19:50
Add a comment
|