Density of universal classes of series-parallel graphs

A class of graphs C ordered by the homomorphism relation is universal if every countable partial order can be embedded in C. It is known (see [1,3]) that the class C-k of k-colorable graphs, for any fixed k >= 3, induces a universal partial order. In [4], a surprisingly small subclass of C-3 which is a proper subclass of the series-parallel graphs (the K-4-minor-free graphs) is shown to be universal. On another side, Pan and Zhu in [7] proved a density result that for each rational number a/b is an element of [2, 8/3] boolean OR {3}, there is a K-4-minor-free graph with circular chromatic number equal to a/b. In this note, we show for each rational number a/b within this interval the class K-a/b of K-4-minor-free graphs with circular chromatic number a/b is universal if and only if a/b not equal 2, 5/2 or 3. This shows yet another surprising richness of the K-4-minor-free class that it contains universal classes as dense as the rational numbers. (C) 2006 Wiley Periodicals, Inc.