Vertex coverings by monochromatic cycles and trees

DOI10.1016/0095-8956(91)90007-7zbMath0766.05062OpenAlexW2057452136WikidataQ105891010 ScholiaQ105891010MaRDI QIDQ1174783

Paul Erdős, András Gyárfás, László Pyber

Publication date: 25 June 1992

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0095-8956(91)90007-7

zbMATH Keywords

pathstreescomplete graphmonochromatic pathsmonochromatic cyclescycle partition numbertree partition numbervertex coverings

Mathematics Subject Classification ID

Trees (05C05) Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Coloring of graphs and hypergraphs (05C15)

Related Items

Generalizations and strengthenings of Ryser's conjecture, Vertex covers by monochromatic pieces -- a survey of results and problems, Dirac-type theorems in random hypergraphs, Monochromatic cycle power partitions, Partitioning complete bipartite graphs by monochromatic cycles, Partitioning 3-edge-coloured complete bipartite graphs into monochromatic cycles, Partitioning two-coloured complete multipartite graphs into monochromatic paths and cycles, Monochromatic Cycle Partitions in Local Edge Colorings, An improved bound for the monochromatic cycle partition number, Monochromatic cycle partitions of graphs with large minimum degree, Decompositions of edge-colored infinite complete graphs into monochromatic paths, Covering complete partite hypergraphs by monochromatic components, Vertex covering with monochromatic pieces of few colours, Partitioning infinite hypergraphs into few monochromatic Berge-paths, Monochromatic tree covers and Ramsey numbers for set-coloured graphs, Exponentially many monochromatic \(n\)-matchings in \(K_{3n-1}\), Decompositions of edge-coloured infinite complete graphs into monochromatic paths. II, Improved monochromatic loose cycle partitions in hypergraphs, Lower bounds on the number of monochromatic matchings in \(K_{2s+t-1}\), Ore- and Pósa-type conditions for partitioning 2-edge-coloured graphs into monochromatic cycles, Partitioning edge-coloured complete graphs into monochromatic cycles and paths, Covering cycles in sparse graphs, A note on covering edge colored hypergraphs by monochromatic components, Monochromatic loose-cycle partitions in hypergraphs, A proof of the Erdős-Faber-Lovász conjecture, Heterochromatic tree partition problem in complete tripartite graphs, Finding large rainbow trees in colourings of \(K_{n, n}\), Minimum degree conditions for tight Hamilton cycles, Minimalist designs, Vertex partitions of non-complete graphs into connected monochromatic \(k\)-regular graphs, Covering Two-Edge-Coloured Complete Graphs with Two Disjoint Monochromatic Cycles, Local colourings and monochromatic partitions in complete bipartite graphs, Powers of Hamilton cycles in random graphs and tight Hamilton cycles in random hypergraphs, Monochromatic partitions in local edge colorings, Minimum degree conditions for monochromatic cycle partitioning, Embedding Graphs into Larger Graphs: Results, Methods, and Problems, Heterochromatic tree partition numbers for complete bipartite graphs, Vertex partitions of \(r\)-edge-colored graphs, Packing the Boolean lattice with copies of a poset, On the minimum monochromatic or multicolored subgraph partition problems, Partitioning 2-edge-colored graphs by monochromatic paths and cycles, Coverings by few monochromatic pieces: a transition between two Ramsey problems, A proof of Ringel's conjecture, Monochromatic cycle partitions of \(2\)-coloured graphs with minimum degree \(3n/4\), Monochromatic bounded degree subgraph partitions, Partitioning random graphs into monochromatic components, The complexity for partitioning graphs by monochromatic trees, cycles and paths, Highly connected monochromatic subgraphs, Heterochromatic tree partition number in complete multipartite graphs, Partitioning 2-edge-colored complete multipartite graphs into monochromatic cycles, paths and trees, Partitioning complete graphs by heterochromatic trees, An Improved Bound for Vertex Partitions by Connected Monochromatic K-Regular Graphs, Partitioning a graph into a cycle and an anticycle, a proof of Lehel's conjecture, Unnamed Item, Partitioning 2-Edge-Colored Ore-Type Graphs by Monochromatic Cycles, Local colourings and monochromatic partitions in complete bipartite graphs, On a Ramsey--Turán Variant of the Hajnal--Szemerédi Theorem, Covering graphs by monochromatic trees and Helly-type results for hypergraphs, Turán density of 2-edge-colored bipartite graphs with application on \(\{2, 3\}\)-hypergraphs, Monochromatic and heterochromatic subgraphs in edge-colored graphs - A survey, Monochromatic square-cycle and square-path partitions, Vertex partitions by connected monochromatic \(k\)-regular graphs, Sprinkling a Few Random Edges Doubles the Power, Monochromatic cycle partitions in random graphs, Covering 3-Edge-Colored Random Graphs with Monochromatic Trees, All Feedback Arc Sets of a Random Turán Tournament Have $\lfloor {n}/{k}\rfloor-{k}+1$ Disjoint ${k}$-Cliques (and This Is Tight), Partitioning a graph into a cycle and a sparse graph, Partitioning Edge-Colored Hypergraphs into Few Monochromatic Tight Cycles, Towards Lehel's conjecture for 4-uniform tight cycles, Almost Partitioning a 3-Edge-Colored $K_{n,n}$ into Five Monochromatic Cycles

Cites Work

• The Ramsey number of a graph with bounded maximum degree
• Maximum degree and fractional matchings in uniform hypergraphs
• On maximal paths and circuits of graphs
• Monochromatic Paths in Graphs
• Vertex coverings by monochromatic paths and cycles
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item