On graphs that can be oriented as diagrams of ordered sets

Abstract

We study some equivalent and necessary conditions for a finite graph to be the covering graph of a (partially) ordered set. For each κ≥1, M. Aigner and G. Prins have introduced a notion of a vertex colouring, here called κ-good colouring, such that a 1-good colouring is the usual concept and graphs that have a 2-good colouring are precisely covering graphs. We present some inequalities for the corresponding chromatic numbers χκ, especially for x 2. There exist graphs that satisfy these inequalities for κ=2 but are not covering graphs. We show also that x 2 cannot be bounded by a function of x=x 1. A construction of Nešetřil and Rödl is used to show that x 2 is not bounded by a function of the girth.