On the critical densities of minor-closed classes
Given a minor-closed class A of graphs, let βAdenote the supremum over all graphs in A of the ratio of edges to vertices. We investigate the set B of all such values βA, taking further the project begun by Eppstein. Amongst other results, we determine the small values in B (those up to 2); we show t...
| Hlavní autoři: | , |
|---|---|
| Médium: | Journal article |
| Vydáno: |
Elsevier
2018
|
| Shrnutí: | Given a minor-closed class A of graphs, let βAdenote the supremum over all graphs in A of the ratio of edges to vertices. We investigate the set B of all such values βA, taking further the project begun by Eppstein. Amongst other results, we determine the small values in B (those up to 2); we show that B is ‘asymptotically dense’; and we answer some questions posed by Eppstein. |
|---|