Partitioning a graph into monochromatic connected subgraphs

DOI10.1002/JGT.22435MaRDI QIDQ5229539zbMATH OpenOpenAlexFDO

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)

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

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)

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.

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

Cited in

(10)

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

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)