Directed subgraph complexes

Axel Hultman

The electronic journal of combinatorics, Tome 11 (2004) no. 1

Résumé

Let $G$ be a directed graph, and let $\Delta^{ACY}_G$ be the simplicial complex whose simplices are the edge sets of acyclic subgraphs of $G$. Similarly, we define $\Delta^{NSC}_G$ to be the simplicial complex with the edge sets of not strongly connected subgraphs of $G$ as simplices. We show that $\Delta^{ACY}_G$ 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^{NSC}_G$ 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.

Détail

DOI : 10.37236/1828

Classification : 05C20, 55P10, 05C40
Mots-clés : directed graph, simplicial complex, homotopy equivalent, chromatic polynomial, hyperplane arrangements.