Monochromatic bounded degree subgraph partitions

DOI10.1016/J.DISC.2015.07.005MaRDI QIDQ501026zbMATH OpenOpenAlexFDO

Authors Andrey Grinshpun, Gábor N. Sárközy

Publication date 8 October 2015

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

Ramsey theoremmonochromatic partitions

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Generalized Ramsey theory (05C55) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: Let $calF=F_1,F_2,ldots$ be a sequence of graphs such that $F_n$ is a graph on $n$ vertices with maximum degree at most $Delta$. We show that there exists an absolute constant $C$ such that the vertices of any 2-edge-colored complete graph can be partitioned into at most $2^{CDeltalogDelta}$ vertex disjoint monochromatic copies of graphs from $calF$. If each $F_n$ is bipartite, then we can improve this bound to $2^{CDelta}$; this result is optimal up to the constant $C$.

Recommendations

• Partitioning a graph into monochromatic connected subgraphs
• Minimum degree conditions for monochromatic cycle partitioning
• Vertex partitions by connected monochromatic \(k\)-regular graphs
• Ramsey problems involving degrees in edge-colored complete graphs of vertices belonging to monochromatic subgraphs
• Monochromatic cycle partitions of \(2\)-coloured graphs with minimum degree \(3n/4\)

Cites work

• scientific article; zbMATH DE number 3652373 (Why is no real title available?)
• scientific article; zbMATH DE number 15152 (Why is no real title available?)
• scientific article; zbMATH DE number 46958 (Why is no real title available?)
• scientific article; zbMATH DE number 3494449 (Why is no real title available?)
• scientific article; zbMATH DE number 3641497 (Why is no real title available?)
• scientific article; zbMATH DE number 1286511 (Why is no real title available?)
• scientific article; zbMATH DE number 878896 (Why is no real title available?)
• scientific article; zbMATH DE number 3344609 (Why is no real title available?)
• 3-uniform hypergraphs of bounded degree have linear Ramsey numbers
• A Fast Approximation Algorithm for Computing the Frequencies of Subgraphs in a Given Graph
• A Short Proof of the Hajnal–Szemerédi Theorem on Equitable Colouring
• A hypergraph blow-up lemma
• An Improved Bound for Vertex Partitions by Connected Monochromatic K-Regular Graphs
• An algorithmic version of the blow-up lemma
• An improved bound for the monochromatic cycle partition number
• Blow-up lemma
• Bounds for graph regularity and removal lemmas
• Covering Two-Edge-Coloured Complete Graphs with Two Disjoint Monochromatic Cycles
• Density theorems for bipartite graphs and related Ramsey-type results
• Embedding and Ramsey numbers of sparse \(k\)-uniform hypergraphs
• Graphs with linearly bounded Ramsey numbers
• Hamiltonian square-paths
• How to avoid using the regularity Lemma: Pósa's conjecture revisited
• Hypergraph packing and sparse bipartite Ramsey numbers
• Improved monochromatic loose cycle partitions in hypergraphs
• Monochromatic cycle partitions of edge-colored graphs
• Monochromatic path and cycle partitions in hypergraphs
• On graphs with linear Ramsey numbers
• On the Ramsey number of sparse 3-graphs
• On the square of a Hamiltonian cycle in dense graphs
• On two problems in graph Ramsey theory
• Partitioning 2-edge-colored graphs by monochromatic paths and cycles
• Partitioning 3-colored complete graphs into three monochromatic cycles
• Partitioning Two-Coloured Complete Graphs into Two Monochromatic Cycles
• Partitioning a graph into a cycle and an anticycle, a proof of Lehel's conjecture
• Partitioning complete bipartite graphs by monochromatic cycles
• Partitioning edge-coloured complete graphs into monochromatic cycles and paths
• Proof of the Seymour conjecture for large graphs
• Pósa's conjecture for graphs of order at least 2 × 10⁸
• Ramsey numbers for sparse graphs
• Ramsey numbers of sparse hypergraphs
• Regular Partitions of Hypergraphs: Regularity Lemmas
• The Ramsey number of a graph with bounded maximum degree
• The Square of a Hamiltonian Cycle
• The square of paths and cycles
• Vertex coverings by monochromatic cycles and trees
• Vertex partitions by connected monochromatic \(k\)-regular graphs

Cited in

(13)

• Minimum degree conditions for monochromatic cycle partitioning
• On graphs with linear Ramsey numbers
• Decomposition of bounded degree graphs into \(C_4\)-free subgraphs
• An Improved Bound for Vertex Partitions by Connected Monochromatic K-Regular Graphs
• Vertex covers by monochromatic pieces -- a survey of results and problems
• Tiling edge-coloured graphs with few monochromatic bounded-degree graphs
• Embedding Graphs into Larger Graphs: Results, Methods, and Problems
• Monochromatic cycle power partitions
• Vertex covering with monochromatic pieces of few colours
• Partitioning edge-colored hypergraphs into few monochromatic tight cycles
• Monochromatic square-cycle and square-path partitions
• Tiling edge-coloured graphs with few monochromatic bounded-degree graphs
• Ore- and Pósa-type conditions for partitioning 2-edge-coloured graphs into monochromatic cycles

This page was built for publication: Monochromatic bounded degree subgraph partitions

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