Dimension,Graph and Hypergraph Coloring |
| |
Authors: | Felsner Stefan Trotter William T |
| |
Institution: | (1) Fachbereich Mathematik und Informatik, Institut für Informatik, Freie Universität Berlin, Takustr. 9, 14195 Berlin, Germany;(2) Department of Mathematics, Arizona State University, Tempe, Arizona, 85287, U.S.A. |
| |
Abstract: | 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 than H
P. We give a new proof of the fact that the dimension of P is 2 if and only if G
P is bipartite. We also show that for each t 2, there exists a poset P
t
for which the chromatic number of the graph of incomparable pairs of P
t
is at most 3 t – 4, but the dimension of P
t
is at least (3 / 2)
t – 1. However, it is not known whether there is a function f: NN 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). |
| |
Keywords: | dimension chromatic number |
本文献已被 SpringerLink 等数据库收录! |
|