# 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
**

**
**