Abstract
For a fixed graph $H$, what is the smallest number of colours $C$ such that
there is a proper edge-colouring of the complete graph $K_n$ with $C$ colours
containing no two vertex-disjoint colour-isomorphic copies, or repeats, of $H$?
We study this function and its generalisation to more than two copies using a
variety of combinatorial, probabilistic and algebraic techniques. For example,
we show that for any tree $T$ there exists a constant $c$ such that any proper
edge-colouring of $K_n$ with at most $c n^2$ colours contains two repeats of
$T$, while there are colourings with at least $c' n^3/2$ colours for some
absolute constant $c'$ containing no three repeats of any tree with at least
two edges. We also show that for any graph $H$ containing a cycle there exist
$k$ and $c$ such that there is a proper edge-colouring of $K_n$ with at most $c
n$ colours containing no $k$ repeats of $H$, while, for a tree $T$ with $m$
edges, a colouring with $o(n^(m+1)/m)$ colours contains $ømega(1)$ repeats
of $T$.
Users
Please
log in to take part in the discussion (add own reviews or comments).