ISSN:
1572-9273
Keywords:
06A10
;
05C20
;
05C38
;
Order
;
diagram
;
graph
;
orientation
;
cycle
Source:
Springer Online Journal Archives 1860-2000
Topics:
Mathematics
Notes:
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.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF00337921
