Density of universal classes of series-parallel graphs

Abstract

A 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.

Keywords

• circular chromatic number
• homomorphism
• series-parallel graphs
• universality
• [info.info-dm] computer science [cs]/discrete mathematics [cs.dm]
• [math.math-co] mathematics [math]/combinatorics [math.co]