Directed subgraph complexes
2004 (English)In: The Electronic Journal of Combinatorics, ISSN 1077-8926, Vol. 11, no 1Article in journal (Refereed) Published
Let G be a directed graph, and let Delta(G)(ACY) be the simplicial complex whose simplices are the edge sets of acyclic subgraphs of G. Similarly, we define Delta(G)(NSC) to be the simplicial complex with the edge sets of not strongly connected subgraphs of G as simplices. We show that Delta(G)(ACY) is homotopy equivalent to the (n-1-k)-dimensional sphere if G is a disjoint union of k strongly connected graphs. Otherwise, it is contractible. If G belongs to a certain class of graphs, the homotopy type of Delta(G)(NSC) is shown to be a wedge of (2n-4)-dimensional spheres. The number of spheres can easily be read off the chromatic polynomial of a certain associated undirected graph. We also consider some consequences related to finite topologies and hyperplane arrangements.
Place, publisher, year, edition, pages
2004. Vol. 11, no 1
connected graphs, orientations, arrangements, topology
IdentifiersURN: urn:nbn:se:kth:diva-23833ISI: 000224701100001OAI: oai:DiVA.org:kth-23833DiVA: diva2:342532
QC 201005252010-08-102010-08-10Bibliographically approved