DMTCS Proceedings, 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)

Font Size:  Small  Medium  Large

Density of universal classes of series-parallel graphs

Jaroslav Nešetřil, Yared Nigussie


A class of graphs C ordered by the homomorphism relation is universal if every countable partial order can be embedded in C. It was shown in [ZH] that the class Ck of k-colorable graphs, for any fixed k≥3, induces a universal partial order. In [HN1], a surprisingly small subclass of C3 which is a proper subclass of K4-minor-free graphs (G/K4) is shown to be universal. In another direction, a density result was given in [PZ], that for each rational number a/b ∈[2,8/3]∪{3}, there is a K4-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 Ka/b of K4-minor-free graphs with circular chromatic number a/b is universal if and only if a/b ≠2, 5/2 or 3. This shows yet another surprising richness of the K4-minor-free class that it contains universal classes as dense as the rational numbers.

Full Text: GZIP Compressed PostScript PostScript PDF original HTML abstract page

Valid XHTML 1.0 Transitional