The size-Ramsey number of powers of bounded degree trees
- Link:
- Autor/in:
- Erscheinungsjahr:
- 2021
- Medientyp:
- Text
- Schlagworte:
-
- Ramsey Number
- Uniform Hypergraph
- Regularity Lemma
- Graph In Graph Theory
- Coloring
- Graphic Methods
- Ramsey Number
- Uniform Hypergraph
- Regularity Lemma
- Graph In Graph Theory
- Coloring
- Graphic Methods
- Beschreibung:
-
Given a positive integer (Formula presented.), the (Formula presented.) -colour size-Ramsey number of a graph (Formula presented.) is the smallest integer (Formula presented.) such that there exists a graph (Formula presented.) with (Formula presented.) edges with the property that, in any colouring of (Formula presented.) with (Formula presented.) colours, there is a monochromatic copy of (Formula presented.). We prove that, for any positive integers (Formula presented.) and (Formula presented.), the (Formula presented.) -colour size-Ramsey number of the (Formula presented.) th power of any (Formula presented.) -vertex bounded degree tree is linear in (Formula presented.). As a corollary, we obtain that the (Formula presented.) -colour size-Ramsey number of (Formula presented.) -vertex graphs with bounded treewidth and bounded degree is linear in (Formula presented.), which answers a question raised by Kamčev, Liebenau, Wood and Yepremyan.
- Lizenz:
-
- info:eu-repo/semantics/openAccess
- Quellsystem:
- Forschungsinformationssystem der UHH
Interne Metadaten
- Quelldatensatz
- oai:www.edit.fis.uni-hamburg.de:publications/b50a2ff8-be1d-4903-9581-448a0e575b1d