Large Monochromatic Triple Stars in Edge Colourings. Issue 4 (19th January 2015) - Letzter, Shoham
Abstract Following problems posed by Gyárfás 2011, we show that for every r‐edge‐colouring of <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgkfp3x738" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />Kn</alternatives> there is a monochromatic triple star of order at least <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgkfp3x717" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />n/(r−1)</alternatives>, 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 <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgkfp3x72r" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />rn/(r2−r+1)</alternatives> vertices in every local r‐colouring of <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgkfp3x76t" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />Kn</alternatives>.