|
|||||
|
|
Partitioning a graph into monochromatic connected subgraphs |
|
| Authors: | António Girão Shoham Letzter Julian Sahasrabudhe |
| Institution: | 1. Department of Pure Mathematics and Mathematical Statistics, University of Cambridge, Cambridge, UK;2. Institute for Theoretical Studies, ETH Zurich, Clausiusstrasse, Zurich, Switzerland;3. Department of Mathematics, University of Memphis, Memphis, Tennessee |
| Abstract: | We show that every  -edge-colored graph on  vertices with minimum degree at least  can be partitioned into two monochromatic connected subgraphs, provided  is sufficiently large. This minimum degree condition is tight and the result proves a conjecture of Bal and DeBiasio. We also make progress on another conjecture of Bal and DeBiasio on covering graphs with large minimum degree with monochromatic components of distinct colors. |
| Keywords: | covering edge colorings monochromatic connected subgraphs partitioning |