A Ramsey type problem concerning vertex colourings
type: Item
instance of: scholarly article
title: A Ramsey type problem concerning vertex colourings
zbMATH Open document ID: 0686.05039
DOI: 10.1016/0095-8956(91)90089-3
author: Jason I. Brown
author: Vojtěch Rödl
published in: Journal of Combinatorial Theory. Series B
publication date: 1991-01-01T00:00:00Z
review text: Let \(H\to^ v_ kG\) denote the fact that for every function \(\pi: V(H)\to \{1,...,k\}\) there is an induced subgraph \(G'\) of H with \(G'\cong G\) and \(V(G')\subseteq \pi^{-1}(i)\) for some i. Folkman has shown that for all graphs G and for all positive integers k such a graph H exists. We examine here f(G,k), the minimum order of a graph H for which \(H\to^ v_ kG\). We show that for any fixed integer \(k\geq 2\) there are positive constants \(C_ 1\) and \(C_ 2\) such that \[ C_ 1n^ 2\leq \max \{f(G,k):\quad | V(G)| =n\}\leq C_ 2n^ 2 \log^ 2 n. \]
Mathematics Subject Classification ID: 05C55
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05A17
zbMATH DE Number: 4123775
zbMATH Keywords: Ramsey theory
zbMATH Keywords: vertex partition
zbMATH Keywords: Folkman graph
MaRDI profile type: Publication
full work available at URL: 0095-8956(91)90089-3
OpenAlex ID: W1989534282
cites work: Eigenvalues, geometric expanders, sorting in rounds, and Ramsey theory
cites work: On size Ramsey number of paths, trees, and circuits. I
cites work: Q3682518
cites work: Graphs with Monochromatic Complete Subgraphs in Every Edge Coloring
cites work: The number of submatrices of a given type in a Hadamard matrix and related results
cites work: Expanding graphs contain all small trees
cites work: Q3331250
cites work: A Ramsey theoretic problem for finite ordered sets
cites work: Selective Graphs and Hypergraphs
description: scientific article; zbMATH DE number 4123775