EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Colorings, transversals, and local sparsity

Ross J. Kang, Tom Kelly

Random Structures & Algorithms · 2022-08 · 61 (1) · 173-192

DOI: 10.1002/rsa.21051 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Random Structures & Algorithms, online erschienen am 13.10.2021. Verfasst von Ross J. Kang und 1 weiteren Autor:innen. Die Arbeit wurde bisher 13-mal zitiert (Crossref) und nennt 22 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Nederlandse Organisatie voor Wetenschappelijk Onderzoek, Engineering and Physical Sciences Research Council.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Motivated both by recently introduced forms of list coloring and by earlier work on independent transversals subject to a local sparsity condition, we use the semi‐random method to prove the following result. For any function satisfying as , there is a function satisfying as such that the following holds. For any graph H and any partition of its vertices into parts of size at least such that (a) for each part the average over its vertices of degree to other parts is at most d , and (b) the maximum degree from a vertex to some other part is at most , there is guaranteed to be a transversal of the parts that forms an independent set of H . This is a common strengthening of two results of Loh and Sudakov (2007) and Molloy and Thron (2012), each of which in turn implies an earlier result of Reed and Sudakov (2002).

Förderung

  • Nederlandse Organisatie voor Wetenschappelijk Onderzoek
  • Engineering and Physical Sciences Research Council

Zitieren

APA

Kang, R. J., & Kelly, T. (2022). Colorings, transversals, and local sparsity. Random Structures & Algorithms, 61(1), 173-192. https://doi.org/10.1002/rsa.21051

Vancouver

Kang RJ, Kelly T. Colorings, transversals, and local sparsity. Random Structures & Algorithms. 2022;61(1):173-192. doi:10.1002/rsa.21051

BibTeX
@article{Kang2022,
  author = {Kang, Ross J. and Kelly, Tom},
  title = {Colorings, transversals, and local sparsity},
  journal = {Random Structures & Algorithms},
  year = {2022},
  volume = {61},
  number = {1},
  pages = {173--192},
  doi = {10.1002/rsa.21051}
}
Kostenlos starten →