https://hal.inria.fr/hal-01184364Nešetřil, JaroslavJaroslavNešetřilKAM - Department of Applied Mathematics (KAM) - Univerzita Karlova v PrazeNigussie, YaredYaredNigussieKAM - Department of Applied Mathematics (KAM) - Univerzita Karlova v PrazeDensity of universal classes of series-parallel graphsHAL CCSD2005universalitycircular chromatic numberhomomorphismseries-parallel graphs[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM][MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO]Episciences Iam, CoordinationStefan Felsner2015-08-14 11:37:352018-09-26 21:52:012015-08-14 16:35:42enConference papershttps://hal.inria.fr/hal-01184364/document10.46298/dmtcs.3407application/pdf1A class of graphs $\mathcal{C}$ ordered by the homomorphism relation is universal if every countable partial order can be embedded in $\mathcal{C}$. It was shown in [ZH] that the class $\mathcal{C_k}$ of $k$-colorable graphs, for any fixed $k≥3$, induces a universal partial order. In [HN1], a surprisingly small subclass of $\mathcal{C_3}$ which is a proper subclass of $K_4$-minor-free graphs $(\mathcal{G/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 $\mathcal{K_{a/b}}$ of $0K_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.