Dimension, Graph and Hypergraph Coloring

Stefan Felsner
Institut für Informatik
Freie Universität Berlin
Takustr. 9, D-14195 Berlin
email: felsner@inf.fu-berlin.de

William T. Trotter
Department of Mathematics
Arizona State University
Tempe, Arizona 85287-1804 U.S.A.
email: trotter@ASU.edu

Report B 98-12
August 1998

There is a natural way to associate with a poset P a hypergraph H_P, called the hypergraph of incomparable pairs, so that the dimension of P is the chromatic number of H_P. The ordinary graph G_P of incomparable pairs determined by the edges in H_P of size 2 can have chromatic number substantially less that H_P. We give a new proof of the fact that the dimensionof P is 2 if and only if G_P is bipartite. We also show that for each t > = 2, there exists a poset P for which the chromatic number of the graph of incomparable pairs is t, but the dimension of P is at least (3/2)^t-1. However, it is not known whether there is a function f: R -> R so that if P is a poset and the graph of incomparable pairs has chromatic number at most t, then the dimension of P is at most f(t).

Get the report here or by anonymous ftp: 
Server: fubinf.inf.fu-berlin.de
File:   pub/reports/tr-b-98-12.ps.gz