Homomorphism thresholds for odd cycles

Link:
Autor/in:
Erscheinungsjahr:
2020
Medientyp:
Text
Beschreibung:
  • The interplay of minimum degree conditions and structural properties of large graphs with forbidden subgraphs is a central topic in extremal graph theory. For a given graph F we define the homomorphism threshold as the infimum over all α ∈ [0,1] such that every n-vertex F-free graph G with minimum degree at least αn has a homomorphic image H of bounded order (i.e. independent of n), which is F-free as well. Without the restriction of H being F-free we recover the definition of the chromatic threshold, which was determined for every graph F by Allen et al. [1]. The homomorphism threshold is less understood and we address the problem for odd cycles.
Lizenz:
  • info:eu-repo/semantics/closedAccess
Quellsystem:
Forschungsinformationssystem der UHH

Interne Metadaten
Quelldatensatz
oai:www.edit.fis.uni-hamburg.de:publications/f4a2f669-172f-456e-bf5d-70a65617451a