On 2-colored graphs and partitions of boxes

DOI10.1016/J.EJC.2019.03.003zbMATH Open1414.05117arXiv1810.08920OpenAlexW2896620677WikidataQ128203071 ScholiaQ128203071MaRDI QIDQ2422239FDOQ2422239

Authors: Ron Holzman 

Publication date: 18 June 2019

Published in: European Journal of Combinatorics (Search for Journal in Brave)

Abstract: We prove that if the edges of a graph G can be colored blue or red in such a way that every vertex belongs to a monochromatic k-clique of each color, then G has at least 4(k-1) vertices. This confirms a conjecture of Bucic, Lidicky, Long, and Wagner (arXiv:1805.11278[math.CO]) and thereby solves the 2-dimensional case of their problem about partitions of discrete boxes with the k-piercing property. We also characterize the case of equality in our result.

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

Recommendations

• Two-colorings with many monochromatic cliques in both colors
• Partitioning a graph into monochromatic connected subgraphs
• Monochromatic cycle partitions of \(2\)-coloured graphs with minimum degree \(3n/4\)
• Unavoidable patterns
• Highly connected monochromatic subgraphs of two-colored complete graphs

zbMATH Keywords

partition problemshigh dimensional boxes

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Cites Work

• Title not available (Why is that?)
• Finite algebras of finite complexity
• Title not available (Why is that?)
• On the decomposition ofkn into complete bipartite graphs
• On partitions of discrete boxes
• Eigensharp Graphs: Decomposition into Complete Bipartite Subgraphs

Cited In (5)

• On \((2,3)\)-agreeable box societies
• Red-blue clique partitions and \((1-1)\)-transversals
• Brick partition problems in three dimensions
• Two-colorings with many monochromatic cliques in both colors
• On partitions of two-dimensional discrete boxes

This page was built for publication: On 2-colored graphs and partitions of boxes

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