On the Structure of Graphs with Given Odd Girth and Large Minimum Degree

Link:
Autor/in:
Erscheinungsjahr:
2015
Medientyp:
Text
Schlagworte:
  • Graph in graph theory
  • Hypergraph
  • R-uniform hypergraph
  • Graph In Graph Theory
  • Coloring
  • Graphic Methods
  • graph homomorphisms
  • Andrasfai-Erdos-Sos theorem
  • extremal graph theory
  • Graph in graph theory
  • Hypergraph
  • R-uniform hypergraph
  • Graph In Graph Theory
  • Coloring
  • Graphic Methods
Beschreibung:
  • We study minimum degree conditions for which a graph with given odd girth has a simple structure. For example, the classical work of Andrasfai, Erdos, and Sos implies that every n- vertex graph with odd girth 2k + 1 and minimum degree bigger than 2/2k+1 n must be bipartite. We consider graphs with a weaker condition on the minimum degree. Generalizing results of Haggkvist and of Haggkvist and Jin for the cases k = 2 and 3, we show that every n- vertex graph with odd girth 2k + 1 and minimum degree bigger than 3/4k n is homomorphic to the cycle of length 2k + 1. This is best possible in the sense that there are graphs with minimum degree 3/4k n and odd girth 2k + 1 that are not homomorphic to the cycle of length 2k + 1. Similar results were obtained by Brandt and Ribe- Baumann. (C) 2014 Wiley Periodicals, Inc.
Lizenz:
  • info:eu-repo/semantics/restrictedAccess
Quellsystem:
Forschungsinformationssystem der UHH

Interne Metadaten
Quelldatensatz
oai:www.edit.fis.uni-hamburg.de:publications/7d37a152-c49f-4178-b622-b0fbd8bd8873