EUVIMEDOpdag EUVIMED
Open access · CC BY 4.0

Universality for Graphs of Bounded Degeneracy

Peter Allen, Julia Böttcher, Anita Liebenau

Random Structures & Algorithms · 2026-03 · 68 (2)

DOI: 10.1002/rsa.70055 ↗

At a glance

Journal article in Random Structures & Algorithms, published online on 2026-03-11. Written by Peter Allen and 2 co-authors. Cited 1 times so far (Crossref); 27 references. The full text is freely available (open access, CC BY 4.0). Funded by: Australian Research Council.

AbstractBibliografiske oplysningerCiteRelated studies

Abstract (original language)

Given a family of graphs, a graph is called ‐universal if contains every graph of as a subgraph. Following the extensive research on universal graphs of small size for bounded‐degree graphs, Alon asked what is the minimum number of edges that a graph must have to be universal for the class of all ‐vertex graphs that are ‐degenerate. In this paper, we answer this question up to a factor that is polylogarithmic in .

Funding

  • Australian Research Council

Cite

APA

Allen, P., Böttcher, J., & Liebenau, A. (2026). Universality for Graphs of Bounded Degeneracy. Random Structures & Algorithms, 68(2). https://doi.org/10.1002/rsa.70055

Vancouver

Allen P, Böttcher J, Liebenau A. Universality for Graphs of Bounded Degeneracy. Random Structures & Algorithms. 2026;68(2). doi:10.1002/rsa.70055

BibTeX
@article{Allen2026,
  author = {Allen, Peter and Böttcher, Julia and Liebenau, Anita},
  title = {Universality for Graphs of Bounded Degeneracy},
  journal = {Random Structures & Algorithms},
  year = {2026},
  volume = {68},
  number = {2},
  doi = {10.1002/rsa.70055}
}
Start for free →