[hal-01184364] Density of universal classes of series-parallel graphs

A class of graphs \mathcalC ordered by the homomorphism relation is \emphuniversal if every countable partial order can be embedded in \mathcalC. It was shown in [ZH] that the class \mathcalC_k of k-colorable graphs, for any fixed k≥3, induces a universal partial order. In [HN1], a surprisingly small subclass of \mathcalC_3 which is a proper subclass of K_4-minor-free graphs (\mathcalG/K_4) 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 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 \mathcalK_a/b of K_4-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 K_4-minor-free class that it contains universal classes as dense as the rational numbers.

from HAL : Dernières publications http://ift.tt/1UIScOo