Monochromatic bounded degree subgraph partitions

Grinshpun, A. and Sárközy, Gábor (2016) Monochromatic bounded degree subgraph partitions. DISCRETE MATHEMATICS, 339 (1). pp. 46-53. ISSN 0012-365X

Preview

Text 1405.7507.pdf Download (178kB) | Preview

Abstract

Abstract Let F = {F1,F2,...} be a sequence of graphs such that Fn 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 2CΔlogΔ vertex disjoint monochromatic copies of graphs from F. If each Fn is bipartite, then we can improve this bound to 2CΔ; this result is optimal up to the constant C. © 2015 Elsevier B.V.

Actions (login required)

Edit Item