Monochromatic bounded degree subgraph partitions

DOI10.1016/J.DISC.2015.07.005zbMATH Open1322.05113arXiv1405.7507OpenAlexW2195803831MaRDI QIDQ501026FDOQ501026

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

Publication date: 8 October 2015

Published in: Discrete Mathematics (Search for Journal in Brave)

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$.

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

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\)

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)

Cites Work

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

Cited In (13)

• Embedding Graphs into Larger Graphs: Results, Methods, and Problems
• Minimum degree conditions for monochromatic cycle partitioning
• 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
• Ore- and Pósa-type conditions for partitioning 2-edge-coloured graphs into monochromatic cycles
• On graphs with linear Ramsey numbers
• Partitioning edge-colored hypergraphs into few monochromatic tight cycles
• Tiling edge-coloured graphs with few monochromatic bounded-degree graphs
• Decomposition of bounded degree graphs into \(C_4\)-free subgraphs
• Vertex covering with monochromatic pieces of few colours
• Monochromatic square-cycle and square-path partitions
• Monochromatic cycle power partitions

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)