Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
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
Identifiers
URN: urn:nbn:se:kth:diva-23833ISI: 000224701100001OAI: oai:DiVA.org:kth-23833DiVA: diva2:342532
Note
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

urn-nbn

Altmetric score

urn-nbn
Total: 18 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf