Monochromatic partitions in 2-edge-coloured bipartite graphs

التفاصيل البيبلوغرافية
العنوان: Monochromatic partitions in 2-edge-coloured bipartite graphs
المؤلفون: Fernández, Camila, Pavez-Signé, Matías, Stein, Maya
سنة النشر: 2024
المجموعة: Mathematics
مصطلحات موضوعية: Mathematics - Combinatorics
الوصف: We study two variations of the Gyarfas--Lehel conjecture on the minimum number of monochromatic components needed to cover an edge-coloured complete bipartite graph. Specifically, we show the following. - For p>> (\log n/n)^{1/2}, w.h.p.~every 2-colouring of the random bipartite graph G~ G(n,n,p) admits a cover of all but O(1/p) vertices of G using at most three vertex-disjoint monochromatic components. - For every 2-colouring of a bipartite graph G with parts of size n and minimum degree (13/16+o(1))n, the vertices of G can be covered using at most three vertex-disjoint monochromatic components.
نوع الوثيقة: Working Paper
URL الوصول: http://arxiv.org/abs/2403.12587
رقم الأكسشن: edsarx.2403.12587
قاعدة البيانات: arXiv