We construct a graph of girth 6 that cannot be oriented as the diagram of an ordered set and discuss the reasons why this particular construction cannot be extended to produce examples of larger girth.
The problem of characterizing graphs that can be oriented as diagrams of ordered sets (or covering graphs) goes back to Ore [5]. It was posed again by Aigner [l] (who mistakenly attributed it to Birkhoff) but it remains unsolved except for special cases. For a survey of the subject see Rival [8]. One of the reasons the problem is so difficult is the fact that non-covering graphs of arbitrarily large girth exist, as was shown by probabilistic arguments by NeSetiil and Rod1 (1978). However, although numerous examples of such graphs of girth 4 have been constructed (see for example Pretzel [7] and NeSetfil [2]), there have been no constructions of examples of higher girth. Indeed in [6] I asked for a 'small' example of a noncovering graph of girth 35.
The graph constructed in this note can hardly be called small, but it is a non-covering graph of girth six. The idea is to start with a graph G of large girth (Y and large chromatic number x. This can be constucted by a method of NeSetiil and Rod1 [4], but the result is always a covering graph, as shown in [7]. To produce a non-covering graph K we erect on each 'long' path P of G a copy of a graph H that ensures that in any diagram orientation P cannot be monotone. The high chromatic number of G requires that any acyclic orientation does have a monotone path P. Thus K cannot be oriented as a diagam. The difficult in this construction is to prevent the girth getting too small. A simple version of this method is used in [7] to produce examples of girth 4 and NeSetiil [2] uses a very clever version of it to show that the problem of determining whether a graph is a covering graph is NP complete.
By using a considerably more sophisticated graph for H, we shall enlarge the girth to 6. However, although it is easy to enlarge the girth of H and G in this construction to any number, the method used here will not produce a graph of girth greater than 6. I shall comment on the reasons for this at the end of this note.
The graph H is illustrated in Fig. 1.