Partitioning a graph into monochromatic connected subgraphs
classification
🧮 math.CO
keywords
graphconnectedmonochromaticsubgraphscolourscompletestatesvariant
read the original abstract
A well-known result by Haxell and Kohayakawa states that the vertices of an $r$-coloured complete graph can be partitioned into $r$ monochromatic connected subgraphs of distinct colours; this is a slightly weaker variant of a conjecture by Erd\H{o}s, Pyber and Gy\'arf\'as that states that there exists a partition into $r-1$ monochromatic connected subgraphs. We consider a variant of this problem, where the complete graph is replaced by a graph with large minimum degree, and prove two conjectures of Bal and DeBiasio, for two and three colours.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.