Directed subgraph complexes
type: Item
instance of: scholarly article
title: Directed subgraph complexes
zbMATH Open document ID: 1060.05038
author: Axel Hultman
published in: The Electronic Journal of Combinatorics
publication date: 2005-04-25T00:00:00Z
full work available at URL: https://eudml.org/doc/124419
full work available at URL: v11i1r75.html
review text: Summary: 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.
Mathematics Subject Classification ID: 05C20
Mathematics Subject Classification ID: 55P10
Mathematics Subject Classification ID: 05C40
zbMATH DE Number: 2161288
zbMATH Keywords: directed graph
zbMATH Keywords: simplicial complex
zbMATH Keywords: homotopy equivalent
zbMATH Keywords: chromatic polynomial
zbMATH Keywords: hyperplane arrangements.
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 2161288