Density of universal classes of series-parallel graphs

✍ Scribed by Jaroslav Nešetřil; Yared Nigussie

• Publisher: John Wiley and Sons
• Year: 2006
• Tongue: English
• Weight: 169 KB
• Volume: 54
• Category: Article
• ISSN: 0364-9024
• DOI: 10.1002/jgt.20182

✦ Synopsis

Abstract

A class of graphs ${\cal C}$ ordered by the homomorphism relation is universal if every countable partial order can be embedded in ${\cal C}$. It is known (see [1,3]) that the class $\cal C_{k}$ of k‐colorable graphs, for any fixed ${k}\geq 3 $, induces a universal partial order. In 4, a surprisingly small subclass of $\cal 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}\in [2,8/3]\cup{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 $\cal K_{a/b} $ of K~4~‐minor‐free graphs with circular chromatic number a/b is universal if and only if $ a/b\neq2 $, 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. © 2006 Wiley Periodicals, Inc. J Graph Theory