Properly coloured copies and rainbow copies of large graphs with small maximum degree

Details Properly coloured copies and rainbow copies of large graphs with small maximum degree Properly coloured copies and rainbow copies of large graphs with small maximum degree

2010-07-21

arxiv.org/abs/1007.3767v1

Mathematics

Combinatorics

9 pages

Scientific paper

Let G be a graph on n vertices with maximum degree D. We use the Lov\'asz local lemma to show the following two results about colourings c of the edges of the complete graph K_n. If for each vertex v of K_n the colouring c assigns each colour to at most (n-2)/22.4D^2 edges emanating from v, then there is a copy of G in K_n which is properly edge-coloured by c. This improves on a result of Alon, Jiang, Miller, and Pritikin [Random Struct. Algorithms 23(4), 409-433, 2003]. On the other hand, if c assigns each colour to at most n/51D^2 edges of K_n, then there is a copy of G in K_n such that each edge of G receives a different colour from c. This proves a conjecture of Frieze and Krivelevich [Electron. J. Comb. 15(1), R59, 2008]. Our proofs rely on a framework developed by Lu and Sz\'ekely [Electron. J. Comb. 14(1), R63, 2007] for applying the local lemma to random injections. In order to improve the constants in our results we use a version of the local lemma due to Bissacot, Fern\'andez, Procacci, and Scoppola [preprint, arXiv:0910.1824].

Affiliated with

Also associated with

No associations

Rating

Properly coloured copies and rainbow copies of large graphs with small maximum degree does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Properly coloured copies and rainbow copies of large graphs with small maximum degree, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Properly coloured copies and rainbow copies of large graphs with small maximum degree will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-610538