2013/10/17 by Shoham Letzter, Letzter, Shoham
Computer Science · Mathematics · #Advanced Graph Theory Research #Limits and Structures in Graph Theory #math.CO
paper · pdf · doi:10.48550/arxiv.1310.4666
arxiv created 2013/10/17 · arxiv updated 2013/10/18
Following problems posed by Gyárfás, we show that for every r-edge-colouring of Kn there is a monochromatic triple star of order at least n/(r-1), improving a previous result by Ruszinkó. An edge colouring of a graph is called a local r-colouring if every vertex spans edges of at most r distinct colours. We prove the existence of a monochromatic triple star with at least rn/(r2-r+1) vertices in every local r-colouring of Kn.