Density of universal classes of series-parallel graphs
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 surpri...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Discrete Mathematics & Theoretical Computer Science
2005-01-01
|
| Series: | Discrete Mathematics & Theoretical Computer Science |
| Subjects: | |
| Online Access: | https://dmtcs.episciences.org/3407/pdf |
| _version_ | 1797270391395188736 |
|---|---|
| author | Jaroslav Nešetřil Yared Nigussie |
| author_facet | Jaroslav Nešetřil Yared Nigussie |
| author_sort | Jaroslav Nešetřil |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-04-25T02:03:31Z |
| format | Article |
| id | doaj.art-f7525afac2c2417c8bc800fe2ade288e |
| institution | Directory Open Access Journal |
| issn | 1365-8050 |
| language | English |
| last_indexed | 2024-04-25T02:03:31Z |
| publishDate | 2005-01-01 |
| publisher | Discrete Mathematics & Theoretical Computer Science |
| record_format | Article |
| series | Discrete Mathematics & Theoretical Computer Science |
| spelling | doaj.art-f7525afac2c2417c8bc800fe2ade288e2024-03-07T14:41:15ZengDiscrete Mathematics & Theoretical Computer ScienceDiscrete Mathematics & Theoretical Computer Science1365-80502005-01-01DMTCS Proceedings vol. AE,...Proceedings10.46298/dmtcs.34073407Density of universal classes of series-parallel graphsJaroslav Nešetřil0Yared Nigussie1Department of Applied Mathematics (KAM)Department of Applied Mathematics (KAM)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.https://dmtcs.episciences.org/3407/pdfcircular chromatic numberhomomorphismseries-parallel graphsuniversality[info.info-dm] computer science [cs]/discrete mathematics [cs.dm][math.math-co] mathematics [math]/combinatorics [math.co] |
| spellingShingle | Jaroslav Nešetřil Yared Nigussie Density of universal classes of series-parallel graphs Discrete Mathematics & Theoretical Computer Science 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] |
| title | Density of universal classes of series-parallel graphs |
| title_full | Density of universal classes of series-parallel graphs |
| title_fullStr | Density of universal classes of series-parallel graphs |
| title_full_unstemmed | Density of universal classes of series-parallel graphs |
| title_short | Density of universal classes of series-parallel graphs |
| title_sort | density of universal classes of series parallel graphs |
| topic | 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] |
| url | https://dmtcs.episciences.org/3407/pdf |
| work_keys_str_mv | AT jaroslavnesetril densityofuniversalclassesofseriesparallelgraphs AT yarednigussie densityofuniversalclassesofseriesparallelgraphs |