Premium
Large Monochromatic Triple Stars in Edge Colourings
Author(s) -
Letzter Shoham
Publication year - 2015
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.21854
Subject(s) - monochromatic color , combinatorics , mathematics , vertex (graph theory) , graph , triple system , enhanced data rates for gsm evolution , star (game theory) , stars , discrete mathematics , physics , computer science , astrophysics , geometry , optics , artificial intelligence , mathematical analysis
Following problems posed by Gyárfás 2011, we show that for every r ‐edge‐colouring of K n there is a monochromatic triple star of order at least n / ( r − 1 ) , improving Ruszinkó's result 2012. 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 r n / ( r 2 − r + 1 ) vertices in every local r ‐colouring of K n .