Change search
ReferencesLink to record
Permanent link

Direct link
Directed subgraph complexes
2004 (English)In: The Electronic Journal of Combinatorics, ISSN 1077-8926, Vol. 11, no 1Article in journal (Refereed) Published
Abstract [en]

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
Keyword [en]
connected graphs, orientations, arrangements, topology
URN: urn:nbn:se:kth:diva-23833ISI: 000224701100001OAI: diva2:342532
QC 20100525Available from: 2010-08-10 Created: 2010-08-10Bibliographically approved

Open Access in DiVA

No full text

Search in DiVA

By author/editor
Hultman, Axel
In the same journal
The Electronic Journal of Combinatorics

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 14 hits
ReferencesLink to record
Permanent link

Direct link