Complete graphs in the plane with colored edges where an edge don't cross edges with same color

Question

The maximal number of nodes in a complete planar graph is $4$.

Suppose that the edges of the graph can be chosen with $m$ different colors and that edges with different colors are allowed to cross each other. What would be the maximal number of nodes for a complete graph like this occurring in the plane with this rule?

Down the case with $2$ colors and $7$ nodes.

I found this: layered graphs, and the results there doesn't contradict a conjecture

A complete graph with $4n$ vertices need n colors for the edges.

Answer 1

A planar graph on n vertices can have at most 3n-6 edges, and so we will need at least $\frac{\binom n2}{3n-6} = \frac{n+1}{6} - \frac{1}{3(n-2)}$ colors.

In the other direction, when $n$ is odd, we can partition $K_n$ into $\frac{n-1}{2}$ Hamiltonian cycles, which are all planar. If we're allowed to curve the edges, we might embed these as follows (example for $K_9$). One cycle looks like:

and the other three cycles are obtained by $45^\circ, 90^\circ, 135^\circ$ rotations of this one. Here is a picture of the full coloring, though there's rather a lot going on:

The construction generalizes to any odd $n$, placing a single vertex in the center of a circle, the others around the perimeter, and zigzagging between them. Except for two edges out of the center and a single edge that would otherwise be a diameter, almost all the edges can be straight lines. This gives us a coloring with $\frac{n-1}{2}$ colors; when $n$ is even, we can color $K_{n+1}$ with $\frac n2$ colors, then delete the center vertex to get a coloring of $K_n$.

So the correct answer is on the order of $cn$ for some constant $c$ between $\frac16$ and $\frac12$.

(If we can't curve the edges, I can't off-hand think of a better thing to do than to partition $K_n$ into $n-1$ perfect matchings for odd $n$, which gives us $n-1$ rather than $\frac{n-1}{2}$ cycles.)

Answer 2

This isn't a complete answer, but the quantity you're asking for is closely related to the thickness of a a graph, which is the minimum number of planar subgraphs which jointly cover the edges of the graph. It is known that the thickness of the complete graph $K_n$ is $\lfloor (n+7)/6 \rfloor$ except at $K_9$ and $K_{10}$.

I believe that the concepts aren't exactly equivalent, because your framing of the question requires all the planar subgraphs to use the same positions for the vertices, while thickness does not require the same restriction. However, the thickness still gives a lower bound on the number of colors required, and it's possible that diving into the papers in the MathWorld article would show that the constructions involved do use the same positions for all the subgraphs (or could be modified in that way).