Naslov
Bounded colorings of multipartite graphs and hypergraphs

Autori
Kamčev, Nina ; Sudakov, Benny ; Volec, Jan

Izvornik
European Journal of Combinatorics (0195-6698) 66 (2017); 235-249

Vrsta, podvrsta i kategorija rada
Radovi u časopisima, članak, znanstveni

Ključne riječi
hamilton cycles

Sažetak
Let c be an edge-coloring of the complete n-vertex graph K-n. The problem of finding properly colored and rainbow Hamilton cycles in c was initiated in 1976 by Bollobas and Eras and has been extensively studied since then. Recently it was extended to. the hypergraph setting by Dudek et al. (2012). We generalize these results, giving sufficient local (resp. global) restrictions on the colorings which guarantee a properly colored (resp. rainbow) copy of a given hypergraph G. We also study multipartite analogues of these questions. We give (up to a constant factor) optimal sufficient conditions for a coloring c of the complete balanced m-partite graph to contain a properly colored or rainbow copy of a given graph G with maximum degree Delta. Our bounds exhibit a surprising transition in the rate of growth, showing that the problem is fundamentally different in the regimes Delta >> m and Delta << m. Our main tool is the framework of Lu and Szekely for the space of random bijections, which we extend to product spaces. Crown Copyright (C) 2017 Published by Elsevier Ltd. All rights reserved.

Izvorni jezik
Engleski

Znanstvena područja
Matematika

POVEZANOST RADA