A note on edge-colourings avoiding rainbow K₄ and monochromatic K_m

Authors Veselin Jungić, Tomáš Kaiser, Daniel Král'

Publication date 26 March 2010

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0902.1608, http://www.emis.de/journals/EJC/Volume_16/Abstracts/v16i1n19.html

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

incidence graphs of finite projective planes mixed Ramsey number

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Generalized Ramsey theory (05C55)

Abstract: We study the mixed Ramsey number maxR(n,K_m,K_r), defined as the maximum number of colours in an edge-colouring of the complete graph K_n, such that K_n has no monochromatic complete subgraph on m vertices and no rainbow complete subgraph on r vertices. Improving an upper bound of Axenovich and Iverson, we show that maxR(n,K_m,K_4) <= n^{3/2}sqrt{2m} for all m >= 3. Further, we discuss a possible way to improve their lower bound on maxR(n,K_4,K_4) based on incidence graphs of finite projective planes.

Review text

Summary: We study the mixed Ramsey number \(\max R(n, K_m, K_r)\), defined as the maximum number of colours in an edge-colouring of the complete graph \(K_n\), such that \(K_n\) has no monochromatic complete subgraph on \(m\) vertices and no rainbow complete subgraph on r vertices. Improving an upper bound of Axenovich and Iverson, we show that \(\max R(n, K_m, K_4) \leq n^{3/2} \sqrt{2m}\) for all \(m \geq 3\). Further, we discuss a possible way to improve their lower bound on \(\max R(n, K_4, K_4)\) based on incidence graphs of finite projective planes.

Recommendations

Cited in

(3)

This page was built for publication: A note on edge-colourings avoiding rainbow \(K_{4}\) and monochromatic \(K_{m}\)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2380208)