Properly edge-coloured subgraphs in colourings of bounded degree
type: Item
instance of: scholarly article
title: Properly edge-coloured subgraphs in colourings of bounded degree
zbMATH Open document ID: 1244.05093
author: Peter Wagner
author: Klas Markström
author: Andrew Thomason
published in: Graphs and Combinatorics
publication date: 2012-01-24T00:00:00Z
review text: The smallest \(n\) such that every coloring of the edges of the \(n\)-vertex complete graph \(K_n\) must contain a monochromatic star \(K_{1,s+1}\) or a properly edge-colored \(K_t\) is denoted by \(f(s,t)\), Its existence is guaranteed by the Erdős-Rado Canonical Ramsey theorem. The authors prove that {\parindent=7mm \begin{itemize}\item[(i)]\(f(s,3)=5s/2+1\) if \(s\) is even and \(f(s,3)=5s/2-1/2\) if \(s\) is odd, \item[(ii)]\((f(2,4)=10\), \item[(iii)]\(f(s,4)\leq 15s/2\), and \item[(iv)]\(f(s,t)\leq 3^52^{-7}(s-1)(t-1)^2+3\). \end{itemize}} The upper bounds for \(f(s,4)\) and \(f(s,t)\) in (iii) and (iv) improve the known upper bounds obtained in [\textit{N. Alon, T. Jiang, Z. Miller} and \textit{D. Pritkin}, ``Properly colored subgraphs and rainbow subgraphs in edge-colorings with local constraints'', Random Struct. Algorithms 23, No. 4, 409--433 (2003; Zbl 1037.05033)]
reviewed by: Van Bang Le
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C55
zbMATH DE Number: 5999823
zbMATH Keywords: properly edge-coloured
zbMATH Keywords: rainbow
zbMATH Keywords: canonical Ramsey theorem
MaRDI profile type: Publication
full work available at URL: s00373-010-0970-5
OpenAlex ID: W2000290050
cites work: Properly colored subgraphs and rainbow subgraphs in edge‐colorings with local constraints
cites work: A Combinatorial Theorem
cites work: Transitiv orientierbare Graphen
cites work: Ramsey numbers for local colorings
cites work: Edge colorings of complete graphs without tricolored triangles
cites work: Constrained Ramsey numbers of graphs
cites work: Q5512796
cites work: On Erdős-Rado numbers
cites work: What we know and what we do not know about Turán numbers
cites work: Q3919732
cites work: Complete graphs with no rainbow path
cites work: An Upper Bound for Constrained Ramsey Numbers
DOI: 10.1007/S00373-010-0970-5
Recommended article: Q4217585
Recommended article: Edge-colored complete graphs with precisely colored subgraphs
Recommended article: Between proper and strong edge‐colorings of subcubic graphs
Recommended article: Between Proper and Strong Edge-Colorings of Subcubic Graphs
Recommended article: Q4504893
Recommended article: Properly colored subgraphs and rainbow subgraphs in edge‐colorings with local constraints
Recommended article: On strong edge-colouring of subcubic graphs
Recommended article: Edge-colouring graphs with bounded local degree sums
Recommended article: Edge-coloured complete graphs: Connectedness of some subgraphs
Recommended article: On the vertex-distinguishing proper edge-colorings of graphs
description: scientific article; zbMATH DE number 5999823