Hypergraph Coloring Complexes

Details Hypergraph Coloring Complexes Hypergraph Coloring Complexes

2011-04-04

arxiv.org/abs/1104.0483v2

Mathematics

Combinatorics

2 figures, small changes and counterexample to a conjecture added

Scientific paper

The aim of this paper is to generalize the notion of the coloring complex of a graph to hypergraphs. We present three different interpretations of those complexes -- a purely combinatorial one and two geometric ones. It is shown, that most of the properties, which are known to be true for coloring complexes of graphs, break down in this more general setting, e.g., Cohen-Macaulayness and partitionabilty. Nevertheless, we are able to provide bounds for the $f$- and $h$-vectors of those complexes which yield new bounds on chromatic polynomials of hypergraphs. Moreover, it is shown that the coloring complex of a hypergraph has a wedge decomposition, though we conjecture that in general this decomposition is not homotopy equivalent to a wedge of spheres. In addition, we can completely characterize those hypergraphs whose coloring complex is connected.

Affiliated with

Also associated with

No associations

Rating

Hypergraph Coloring Complexes does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Hypergraph Coloring Complexes, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Hypergraph Coloring Complexes will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-317366