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.
