Monochromatic bounded degree subgraph partitions

2014/05/29 by Andrey Grinshpun, Grinshpun, Andrey, Gábor N. Sárközy +1
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Digital Image Processing Techniques #FOS: Mathematics #Limits and Structures in Graph Theory

paper · doi:10.48550/arxiv.1405.7507

openalex publication_date 2014/05/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Let \calF=\F₁,F₂,…\ be a sequence of graphs such that F_n is a graph on n vertices with maximum degree at most Δ. 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^CΔlogΔ vertex disjoint monochromatic copies of graphs from \calF. If each F_n is bipartite, then we can improve this bound to 2^{C Δ}; this result is optimal up to the constant C.

Citations

• A quantitative version of the Blow-up Lemma
• On a Problem of Formal Logic

Related

• Minimum degree conditions for monochromatic cycle partitioning
• Tiling with monochromatic bipartite graphs of bounded maximum degree
• Tiling edge-coloured graphs with few monochromatic bounded-degree graphs
• Partitioning a graph into monochromatic connected subgraphs
• Partitioning a 2-edge-coloured graph of minimum degree 2n/3 + o(n) into three monochromatic cycles