Loading [MathJax]/jax/output/HTML-CSS/jax.js

Jaroslav Nešetřil ; Yared Nigussie - Density of universal classes of series-parallel graphs

dmtcs:3407 - Discrete Mathematics & Theoretical Computer Science, January 1, 2005, DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05) - https://doi.org/10.46298/dmtcs.3407
Density of universal classes of series-parallel graphsConference paper

Authors: Jaroslav Nešetřil ORCID1; Yared Nigussie 1

  • 1 Department of Applied Mathematics (KAM)

A class of graphs C ordered by the homomorphism relation is universal if every countable partial order can be embedded in C. It was shown in [ZH] that the class Ck of k-colorable graphs, for any fixed k3, induces a universal partial order. In [HN1], a surprisingly small subclass of C3 which is a proper subclass of K4-minor-free graphs (G/K4) 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 K4-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 Ka/b of 0K4-minor-free graphs with circular chromatic number a/b is universal if and only if a/b2, 5/2 or 3. This shows yet another surprising richness of the K4-minor-free class that it contains universal classes as dense as the rational numbers.


Volume: DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)
Section: Proceedings
Published on: January 1, 2005
Imported on: May 10, 2017
Keywords: universality,circular chromatic number,homomorphism,series-parallel graphs,[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM],[MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO]

Consultation statistics

This page has been seen 254 times.
This article's PDF has been downloaded 422 times.