Partitioning by monochromatic trees
From MaRDI portal
Any \(r\)-edge-coloured \(n\)-vertex complete graph \(K^n\) contains at most \(r\) monochromatic trees, all of different colours, whose vertex sets partition the vertex set of \(K^n\), provided \(n\geq 3r^4r!(1-1/r)^{3(1-r)}\log r\). This comes close to proving, for large \(n\), a conjecture of \textit{P. Erdös}, \textit{A. Gyárfás} and \textit{L. Pyber} [J. Comb. Theory, Ser. B 51, No. 1, 90-95 (1991; Zbl 0766.05062)], which states that \(r-1\) trees suffice for all \(n\).
Recommendations
- Partitioning complete multipartite graphs by monochromatic trees
- Vertex coverings by monochromatic cycles and trees
- Partitioning 3-edge-colored complete equi-bipartite graphs by monochromatic trees under a color degree condition
- Partitioning edge-coloured complete graphs into monochromatic cycles and paths
Cited in
(26)- Partitioning 3-edge-colored complete equi-bipartite graphs by monochromatic trees under a color degree condition
- Monochromatic and heterochromatic subgraphs in edge-colored graphs - A survey
- Monochromatic trees with respect to edge partitions
- Partitioning complete bipartite graphs by monochromatic cycles
- Covering graphs by monochromatic trees and Helly-type results for hypergraphs
- Generalizations and strengthenings of Ryser's conjecture
- Monochromatic partitions in local edge colorings
- Heterochromatic tree partition number in complete multipartite graphs
- Monochromatic tree covers and Ramsey numbers for set-coloured graphs
- On the minimum monochromatic or multicolored subgraph partition problems
- Highly connected monochromatic subgraphs
- Partitioning 2-edge-colored complete multipartite graphs into monochromatic cycles, paths and trees
- The colour lemma. A combinatorial result and its application to tree partitions
- Vertex covers by monochromatic pieces -- a survey of results and problems
- Heterochromatic tree partition problem in complete tripartite graphs
- The complexity for partitioning graphs by monochromatic trees, cycles and paths
- Partitioning complete multipartite graphs by monochromatic trees
- Covering 3-edge-colored random graphs with monochromatic trees
- Partitioning random graphs into monochromatic components
- Ore- and Pósa-type conditions for partitioning 2-edge-coloured graphs into monochromatic cycles
- Tiling edge-coloured graphs with few monochromatic bounded-degree graphs
- Tiling edge-coloured graphs with few monochromatic bounded-degree graphs
- Monochromatic partitions in 2-edge-coloured bipartite graphs
- Partitioning complete graphs by heterochromatic trees
- Heterochromatic tree partition numbers for complete bipartite graphs
- Vertex partitions of \(r\)-edge-colored graphs
This page was built for publication: Partitioning by monochromatic trees
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1125948)
