# Coloring a polyomino tiling so that no two pieces with the same color have a common point

How many colors are enough to color all polyomino tilings so that no two adjacent or touching polyominoes have the same color? In the following example 6 colors are required (each region has a common point with every other region). Are there tilings that cannot be colored with 6 colors?

5 5 6 6
5 1 2 6
5 3 4 6
5 5 6 6


The polyomino tilings induce 1-planar graphs. It was shown by [1] that these graphs are 6-colorable, but the proof is really involved and uses the same techniques as the infamous 4-colour theorem, though which much less reducible configurations. The proof is already quite involved for just proving that the graph is $$7$$-colorable.

Still, we can easily show that $$1$$-planar graphs are 8-colorable:

Let $$G$$ be a maximal $$1$$-planar graph with $$n$$ vertices and $$m$$ edges. By removing one edge for each crossing pair of edges, we get a maximal planar graph $$G'$$ with $$n'=n$$ vertices, $$m' = m-c$$ edges where $$c$$ is the number of edges removed and $$f'$$ faces.

We know by Euler formula that $$m'\leq 3n'-6$$ and $$f' = 2n'-4$$ . So $$m = m'+c \leq 3n'-6 + f'/2 = 4n'-8$$ (each removed edge cross two faces, on face can only be crossed by one edge)

The average degree is $$\frac{2m}{n} < 8$$, so there exist a vertex of degree $$7$$. Hence $$1$$-planar graphs are $$7$$-degenerate, so $$8$$-colorable. (See [2])

[1]: Borodin, O. V., Solution of Ringel’s problems concerning the vertex-faced coloring of planar graphs and the coloring of 1-planar graphs, Metody Diskretn. Anal. 41, 12-26 (1984). ZBL0565.05027.

[2]: Fabrici, Igor; Madaras, Tomáš, The structure of 1-planar graphs, Discrete Math. 307, No. 7-8, 854-865 (2007). ZBL1111.05026.