Idioma:

Minimum degree conditions for monochromatic cycle partitioning

Korándi, Dániel ; Lang, Richard ; Letzter, Shoham ; Pokrovskiy, Alexey

Journal of combinatorial theory. Series B, 2021-01, Vol.146, p.96-123 [Periódico revisado por pares]

Texto completo disponível

Citações Citado por

Título:
Minimum degree conditions for monochromatic cycle partitioning
Autor: Korándi, Dániel ; Lang, Richard ; Letzter, Shoham ; Pokrovskiy, Alexey
Assuntos: Dirac-type problems ; Hamilton cycles ; Monochromatic cycle partitioning ; Ramsey theory
É parte de: Journal of combinatorial theory. Series B, 2021-01, Vol.146, p.96-123
Descrição: A classical result of Erdős, Gyárfás and Pyber states that any r-edge-coloured complete graph has a partition into O(r2log⁡r) monochromatic cycles. Here we determine the minimum degree threshold for this property. More precisely, we show that there exists a constant c such that any r-edge-coloured graph on n vertices with minimum degree at least n/2+c⋅rlog⁡n has a partition into O(r2) monochromatic cycles. We also provide constructions showing that the minimum degree condition and the number of cycles are essentially tight.
Editor: Elsevier Inc
Idioma: Inglês

Voltar para lista de resultados

Anterior Resultado 10 Avançar Ir para próxima página