On 2-colored graphs and partitions of boxes

DOI10.1016/J.EJC.2019.03.003MaRDI QIDQ2422239zbMATH OpenOpenAlexWikidataFDO

Authors Ron Holzman

Publication date 18 June 2019

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

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

zbMATH Keywords

partition problemshigh dimensional boxes

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

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.

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

Cites work

• scientific article; zbMATH DE number 3430675 (Why is no real title available?)
• scientific article; zbMATH DE number 3395950 (Why is no real title available?)
• Eigensharp Graphs: Decomposition into Complete Bipartite Subgraphs
• Finite algebras of finite complexity
• On partitions of discrete boxes
• On the decomposition ofkn into complete bipartite graphs

Cited in

(5)

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

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)