Rainbow subgraphs of star-coloured graphs
Preprint
Abstract
An edge-colouring of a graph $G$ can fail to be rainbow for two reasons: either it contains a monochromatic cherry (a pair of incident edges), or a monochromatic matching of size two. A colouring is a proper colouring if it forbids the first structure, and a star-colouring if it forbids the second structure. In this paper, we study rainbow subgraphs in star-coloured graphs and determine the maximum number of colours in a star-colouring of a large complete graph which does not contain a rainbow copy of a given graph $H$. This problem is a special case of one studied by Axenovich and Iverson on generalised Ramsey numbers and we extend their results in this case.
Keywords
All Related Versions
This publication has 22 references indexed in Scilit:
- Random subgraphs of properly edge-coloured complete graphs and long rainbow cyclesIsrael Journal of Mathematics, 2017
- Rainbow Numbers for Graphs Containing Small CyclesGraphs and Combinatorics, 2015
- Dependent random choiceRandom Structures & Algorithms, 2010
- Rainbow Generalizations of Ramsey Theory: A SurveyGraphs and Combinatorics, 2010
- Constrained Ramsey numbers of graphsJournal of Graph Theory, 2002
- An Anti-Ramsey TheoremCombinatorica, 2002
- The Moore Bound for Irregular GraphsGraphs and Combinatorics, 2002
- Norm-graphs and bipartite tur n numbersCombinatorica, 1996
- An inequality involving the vertex arboricity and edge arboricity of a graphJournal of Graph Theory, 1986
- Über ein Problem von K. ZarankiewiczActa Mathematica Hungarica, 1958