Size of monochromatic double stars in edge colorings
type: Item
instance of: scholarly article
title: Size of monochromatic double stars in edge colorings
zbMATH Open document ID: 1177.05040
author: András Gyárfás
author: Gábor N. Sárközy
published in: Graphs and Combinatorics
publication date: 2009-05-08T00:00:00Z
review text: It is well-known that there is a monochromatic spanning tree for every 2-coloring of the edges of a complete graph. An earlier result of the first author is the following theorem: If the edges of a complete graph \(K_n\) on \(n\) vertices are coloured with \(r\) colours, then there is a monochromatic subtree with at least \(\frac{n}{r-1}\) vertices. In the present paper, the authors show that for every \(r\)-colouring of the edges of \(K_n\) there is a monochromatic double star with at least \(\frac{n(r+1)+r-1}{r^2}\) vertices. Its is shown that this result is sharp in asymptotic for \(r= 2\). For \(r\geq 3\) it improves a known bound for the largest monochromatic subgraph of diameter at most 3. When \(r\)-colorings are replaced by local \(r\)-colorings, the bound is \(\frac{n(r+1)+r-1}{r^2+ 1}\).
reviewed by: Ulrike Baumann
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C05
zbMATH DE Number: 5552213
zbMATH Keywords: edge coloring
zbMATH Keywords: complete graph
zbMATH Keywords: nonchromatic tree
zbMATH Keywords: monochromatic double star
MaRDI profile type: Publication
full work available at URL: s00373-008-0811-y
OpenAlex ID: W2045725258
cites work: Highly connected monochromatic subgraphs
cites work: Domination in colored complete graphs
cites work: Finding large \(p\)-colored diameter two subgraphs
cites work: Maximum degree and fractional matchings in uniform hypergraphs
cites work: Generalized Ramsey theory for graphs, X: Double stars
cites work: Ramsey numbers for local colorings
cites work: Edge colorings of complete graphs without tricolored triangles
cites work: Size of monochromatic components in local edge colorings
cites work: Highly connected multicoloured subgraphs of multicoloured graphs
cites work: Generalizing the Ramsey problem through diameter
DOI: 10.1007/S00373-008-0811-Y
description: scientific article; zbMATH DE number 5552213