On the local density problem for graphs of given odd-girth

Link:
Autor/in:
Erscheinungsjahr:
2019
Medientyp:
Text
Schlagworte:
  • Andrasfai graphs
  • Erdos (1/2,1/50)-conjecture
  • sparse halves
  • triangle-free graphs
Beschreibung:
  • Erdős conjectured that every n-vertex triangle-free graph contains a subset of [η/2] vertices that spans at most η2/50 edges. Extending a recent result of Norin and Yepremyan, we confirm this conjecture for graphs homomorphic to so-called Andrásfai graphs. As a consequence, Erdős' conjecture holds for every triangle-free graph G with minimum degree δ(G) > 10η/29 and if χ(G) ≤ 3 the degree condition can be relaxed to δ(G) > η/3. In fact, we obtain a more general result for graphs of higher odd-girth.
Lizenz:
  • info:eu-repo/semantics/restrictedAccess
Quellsystem:
Forschungsinformationssystem der UHH

Interne Metadaten
Quelldatensatz
oai:www.edit.fis.uni-hamburg.de:publications/77557479-3337-4af3-b536-fe3862d77a77