Edge Colourings of Graphs Avoiding Monochromatic Matchings of a Given Size

Let k and l be positive integers. With a graph G, we associate the quantity c(k,l)(G), the number of k-colourings of the edge set of G with no monochromatic matching of size l. Consider the function c(k,l) : N --> N given by c(k,l)(n) = max {c(k,l)(G): vertical bar V(G)vertical bar = n}, the maximum of c(k,l)(G) over all graphs G on n vertices. In this paper, we determine c(k,l)(n) and the corresponding extremal graphs for all large n and all fixed values of k and l.

FAPERGS [Proc. 11/1436-1]

FAPERGS

CNPq [Proc. 484154/2010-9, Proc. 308509/2007-2, 484154/2010-9]

CNPq

University of Sao Paulo

University of Sao Paulo