How many integer colours are sufficient to colour an \(n\)-vertex planar graph so that the maximum colour encountered along any path of length at most 2 occurs only once along that path? It turns out that the correct answer is \(\Theta(\log n/\log\log\log n)\). The triple-log comes from the fact every planar graph is contained in the strong product of a planar 3-tree and a very simple graph.

· · Web · 0 · 0 · 2
Sign in to participate in the conversation

The social network of the future: No ads, no corporate surveillance, ethical design, and decentralization! Own your data with Mastodon!