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

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.

• Interesting. For $m=2$ I can do $6$ nodes. Haven't tried $7$. Can you work out this case and edit your question to include the result? You could ask about bipartite graphs too. – Ethan Bolker Jan 24 '18 at 15:04
• @EthanBolker: For $m=2$ I did $7$ nodes by marking the nodes on both sides of a paper and write edges on the both sides. – Lehs Jan 24 '18 at 17:15

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.)

• Note that even though Hamiltonian cycles are planar graphs, there's no guarantee that an arbitrary Hamiltonian cycle in an already-embedded plane graph will be noncrossing with respect to that particular embedding of the vertices. – Gregory J. Puleo Jan 24 '18 at 17:28
• @GregoryJ.Puleo True in general, but in this case it's possible; I guess I should elaborate on how. – Misha Lavrov Jan 24 '18 at 17:41
• I see your point. The illustration is very helpful! – Gregory J. Puleo Jan 24 '18 at 17:58

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).

• What difference could the positions of the vertices possibly make? Unless you require the edges to be drawn as straight lines, but it's apparent from the OP's drawing that that's not a requirement. Given a set of $n$ distinct points $x_1,\dots,x_n,$ and another set of $n$ distinct points $y_1,\dots,y_n,$ there is a homeomorphism of the plane to itself mapping $x_i$ to $y_i$ for $i=1,\dots,n.$ – bof Jan 24 '18 at 20:25
• @bof I'm not particularly well-versed in topology per se, so I stuck to what I knew was true, and it wasn't immediately obvious to me that a planar graph can have its edges drawn in a noncrossing manner no matter how the vertices are placed into the plane. Based on what you're saying, it sounds like thickness might actually be the beginning and the end of the story here. – Gregory J. Puleo Jan 24 '18 at 23:03