Partitioning a graph into monochromatic connected subgraphs

DOI10.1002/JGT.22435zbMATH Open1417.05166arXiv1708.01284OpenAlexW2963274697MaRDI QIDQ5229539FDOQ5229539

Authors: António Girão, Shoham Letzter, Julian Sahasrabudhe 

Publication date: 15 August 2019

Published in: Journal of Graph Theory (Search for Journal in Brave)

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 ErdH{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.

Full work available at URL: https://arxiv.org/abs/1708.01284

Recommendations

• Monochromatic cycle partitions of \(2\)-coloured graphs with minimum degree \(3n/4\)
• Large monochromatic components in multicolored bipartite graphs
• Minimum degree conditions for monochromatic cycle partitioning
• Ore- and Pósa-type conditions for partitioning 2-edge-coloured graphs into monochromatic cycles
• Large monochromatic components in edge colored graphs with a minimum degree condition

zbMATH Keywords

coveringedge coloringspartitioningmonochromatic connected subgraphs

Mathematics Subject Classification ID

Connectivity (05C40) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cited In (9)

• Generalizations and strengthenings of Ryser's conjecture
• Monochromatic bounded degree subgraph partitions
• Monochromatic cycle partitions of \(2\)-coloured graphs with minimum degree \(3n/4\)
• Ore- and Pósa-type conditions for partitioning 2-edge-coloured graphs into monochromatic cycles
• Large monochromatic components in almost complete graphs and bipartite graphs
• Large monochromatic components in multicolored bipartite graphs
• On 2-colored graphs and partitions of boxes
• Balancing connected colourings of graphs
• Covering graphs by monochromatic trees and Helly-type results for hypergraphs

This page was built for publication: Partitioning a graph into monochromatic connected subgraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5229539)