A square-grid coloring problem

MaRDI QIDQ5133130zbMATH OpenFDO

Authors Matthew Kahle, Francisco Martinez-Figueroa, Alexander Soifer

Publication date 12 November 2020

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

zbMATH Keywords

\(a\)-coloringcomplete coloringgrids

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Abstract: Suppose that $nge2$, and we wish to plant $k$ different types of trees in the squares of an $nimesn$ square grid. We can have as many of each type as we want. The only rule is that every pair of types must occur in an adjacent pair of squares somewhere in the grid. The question is: given $n$, what is the largest that $k$ can be? Denote this number by $Gamma(n)$, and call this the *complete coloring number* of the $nimesn$ grid. A little thought shows that $Gamma(n)le2n-1$. The main question we are interested in is whether $Gamma(n)=2n-1$ for every $nge2$.

Recommendations

• Rectangle-free colorings of extremely complex grids using 4 colors
• On some coloring problems in grids
• Matricial construction of k-colourings on square lattice.
• Adjacent vertex-distinguishing edge colorings of a class of two dimensional generalized grid graphs generated by complete graphs
• Grid drawings of \(k\)-colourable graphs

Cited in

(6)

• Coloring grids
• How many ways can you color your turkey? Counting the proper colorings of a grid graph
• Rectangle-free colorings of extremely complex grids using 4 colors
• Highly complex 4-colored rectangle-free grids -- solution unsolved multiple-valued problems
• The painter's problem: covering a grid with colored connected polygons
• scientific article; zbMATH DE number 7103733 (Why is no real title available?)

This page was built for publication: A square-grid coloring problem

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