Skip to Main content Skip to Navigation
Conference papers

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.
Complete list of metadata

Cited literature [10 references]  Display  Hide  Download

https://hal.inria.fr/hal-01184364
Contributor : Coordination Episciences Iam <>
Submitted on : Friday, August 14, 2015 - 11:37:35 AM
Last modification on : Wednesday, September 26, 2018 - 9:52:01 PM
Long-term archiving on: : Sunday, November 15, 2015 - 11:01:22 AM

File

dmAE0149.pdf
Publisher files allowed on an open archive

Identifiers

  • HAL Id : hal-01184364, version 1

Collections

Citation

Jaroslav Nešetřil, Yared Nigussie. Density of universal classes of series-parallel graphs. 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), 2005, Berlin, Germany. pp.245-250. ⟨hal-01184364⟩

Share

Metrics

Record views

360

Files downloads

805