Plane colorings

[skeptical scientist]

Sadly, I don't think they're closed under taking minors, so we can't rely on

http://en.wikipedia.org/wiki/Robertson-Seymour_theorem

There are clearly a few easy forbidden subgraphs, like K_4, or a square pyramid, but that's not going to get us anywhere quickly imo.

It is the right question though. The answer is probably something to do with triangles.

/stating the obvious.

I didn't ask for an efficient algorithm, it doesn't have to be as simple as "check whether the graph contains a copy of X, Y, or Z". Just an algorithm witnessing that the problem is decidable. And it can't possibly fail to be decidable, right? That would just be weird.

One avenue for finding an algorithm would be noticing that to finding an embedding of an n-vertex graph is equivalent to finding a real solution for a particular system of polynomial equations in 2n variables (or 2n-4, since WLOG the first two points are (0,0) and (0,1)). Are there known algorithms for this? I'm pretty sure that if a solution exists, a solution can be found inside the algebraics, and you should be able to bound the degrees of the minimal polynomials. If you can also bound the coefficients of the minimal polynomials, you can probably do brute-force checking with a computer algebra system.

* * *

As a side-note, the class of embeddable graphs is so badly not closed under minors that every graph is the minor of an embeddable graph. Given any graph, if you replace all edges with paths of length 2, the resulting graph is embeddable.

[Proginoskes]

Something like this has been known for decades:

If there is a number K such that every finite "unit distance" graph is K-colorable, then the entire plane is K-colorable.

One of Erdos's many results ...

In fact, I gave a proof earlier in this very thread.

Whaaa...? Oops, time to take my ADHD medication ...

On a semi-related note, does anyone know an algorithm which, given some description of a graph, will decide whether it's embeddable in the unit-distance plane graph?

MathWorld --- http://mathworld.wolfram.com/Unit-DistanceGraph.html --- has a list of papers. MathSciNet would also be a good place to go searching.

Hochburg's A Program for Proving That a Given Graph Is Not a Unit-Distance Graph claims that there is an algorithm to prove that a certain graph is not a unit-distance graph. According to the abstract, "The algorithm described is not quite brute force."

[skeptical scientist]

In quick skimming, it appears that checking whether a graph has a drawing with all edges unit distance is NP-hard. This doesn't tell us whether it's computable, but it does show that brute-force computation of tomtom's f will be slow. (Even though f is actually computable in O(1) time!--we just don't know the algorithm.)

[tomtom2357]

In quick skimming, it appears that checking whether a graph has a drawing with all edges unit distance is NP-hard. This doesn't tell us whether it's computable, but it does show that brute-force computation of tomtom's f will be slow. (Even though f is actually computable in O(1) time!--we just don't know the algorithm.)

This is why I like (trying to at least) solving previously unsolved problems using functions, I usually end up creating NP-Hard problems in either computing the function or in a brute-force solution.

[Proginoskes]

In quick skimming, it appears that checking whether a graph has a drawing with all edges unit distance is NP-hard. This doesn't tell us whether it's computable, but it does show that brute-force computation of tomtom's f will be slow. (Even though f is actually computable in O(1) time!--we just don't know the algorithm.)

I read somewhere that determining whether x^2 + y^2 = 1 is undecidable (if x and y are given in decimal notation), so in order for it to be in NP, you'd need finite representations.

[skeptical scientist]

I read somewhere that determining whether x^2 + y^2 = 1 is undecidable (if x and y are given in decimal notation), so in order for it to be in NP, you'd need finite representations.

Equality in general is an incomputable function on R², just because every computable function from Rⁿ to R is continuous.

This isn't really relevant for the graph problem though because the question is whether a graph (a finite object) is embeddable in the unit-distance-plane graph (a yes or no question). Everything deals with finite objects, so you don't ever need to think about infinite objects like decimal representations.

[tomtom2357]

I came up with a new idea: In the unit-distance graphs that prove that at least 4 colors are needed, every point had this property: every point was connected to at least three other points. After a bit of thinking I realized the reason for this was that every point that is not connected to three other points, is not needed in the graph, because it could always be given one of the three assumed colors that it is not a unit distance away from. This can be extended, to show that in a hypothetical unit-distance graph that cannot be 4-colored, every point needs to be connected to at least 4 other points. This should narrow down the amount of graphs that need to be checked. Also that set of graphs contains a lot of non-plane embeddable graphs, so that would narrow it down even further!

I have a few proofs that follow from this lemma, the most notable being: If a unit-distance plane graph is not four colorable, and it is embeddable in the plane, then for every point on the graph, there is a point that is not directly connected to it (a.k.a. not connected by a line). Proof: Assume that there is a point that is connected to every other point on the graph. Lets call this point A. Now we pick another point on the graph and call it B. Now, since this graph is not 4-colorable, every point is connected to at least four other points. Therefore B is connected to A and at least 3 other points (call these C, D, and E). These points are also connected to A, by the original assumption. But three points either define a line, in which case no point is at unit distance from all of them, or they are not in a straight line, in which case they define a unique circle. Since there is a unique circle, there is a unique point that is equidistant from all of them. But this is impossible, since A and B are both equidistant from all of them, a contradiction. Therefore for every point, there is at least one point that is not at unit distance from it.

Edit: actually, my proof can be extended to show that for every point (in the unit distance graph that is embeddable in the plane), there are at least 2 points that are not at unit distance from it. All you have to do is assume that only one point is not connected to A, and change my proof slightly and make that point B, and the exact same contradiction follows.

Edit2: I have now proved that f(3)=f(4)=f(5)=f(6)=3! So that means that there is no simpler graph than the moser spindle that shows that the chromatic number of the plane is at least 4. I am in the middle of trying to figure out if f(7) is really 4, or if it is 5.

[mfb]

This can be extended, to show that in a hypothetical unit-distance graph that cannot be 4-colored, every point needs to be connected to at least 4 other points.

No, this direction does not work. For every unit-distance graph that cannot be 4-colored, you can add a new vertex which is connected to a single other vertex only. The new graph cannot be 4-colored, but one vertex has just one edge.
However, if there is a graph which cannot be 4-colored, you can remove all points with less than 4 edges, without losing this property.

[tomtom2357]

This can be extended, to show that in a hypothetical unit-distance graph that cannot be 4-colored, every point needs to be connected to at least 4 other points.

No, this direction does not work. For every unit-distance graph that cannot be 4-colored, you can add a new vertex which is connected to a single other vertex only. The new graph cannot be 4-colored, but one vertex has just one edge.
However, if there is a graph which cannot be 4-colored, you can remove all points with less than 4 edges, without losing this property.

Oops, sorry, I meant that for every graph that cannot be 4-colored, either every point has four points that it is connected to, or that there is a sub-graph of that graph that cannot be four colored such that every point is connected to four other points. I am interested in a minimal graph that cannot be four-colored, not all the other graphs that can be made from that graph by attaching new vertices. I thought it would be useful to list on this forum any unit-distance graphs you can think of that cannot be embedded in the plane. Labeling the points A, B, C, etc and listing the vertices of the unembeddable graphs, I have:

The tetrahedron: {AB,AC,AD,BC,BD,CD}
I don't exactly know what to call this, so I'll just call it U₁: {AB,AC,AD,BE,CE,DE}
Edit: I just came up with a whole class of unembeddable graphs:
pentagonal pyramid:{AB,AC,AD,AE,AF,BC,BF,CD,DE,EF}
septagonal pyramid:{AB,AC,AD,AE,AF,AG,AH,BC,BH,CD,DE,EF,FG,GH}
and so on, basically, A is connected to every point, B is connected to the last point, and every point is connected to the point before or after it in the loop of all points but A. This doesn't work with 7 points (including A), because that is just a hexagon with A in the middle.

Any more you can think of? I didn't include the square pyramid on purpose because it turns out that U₁ is a sub-graph of the square pyramid.

Also, I have a proof that any unit-distance graph that is unembeddable in the plane must have a point that is connected to at least 3 other points. It goes as follows: assume that it is possible to have an unembeddable graph that has no points connected to more than 2 other points. Every point that is only connected to one other point can be removed from the graph without compromising its unembeddability, so we can assume that every point is connected to exactly 2 other points. no small loops can exist in the graph, because then every point in that sub-graph is connected to 2 other points in that sub-graph, and it cannot be connected to the rest of the original graph, meaning that either the sub-graph, or the rest of the graph, can be removed from the graph. This means that there is one big loop in the graph, containing all the points.

However, this can be embedded as a polygon in the plane, therefore there is no minimal graph satisfying the assumptions, therefore there is no graph such that every point is connected to at most two other points that is not embeddable in the plane.

[tomtom2357]

I came up with a proof that for every point in a unit distance, plane-embeddable, minimal non-four-colorable graph (every sub-graph is four-colorable), there are at least 3 points not adjacent to it. The proof goes as follows: Assume (to get a contradiction) there is a point that is connected to all but two other points (I already proved earlier that there are at least two points that this point is not adjacent to). Call this point A, and the tow points it is not connected to B and C. Now, whether or not B and C are adjacent, there are at least three other points B is connected to, because every point in a minimal non-four-colorable graph is adjacent to at least four other points. Therefore B is adjacent to three points A is adjacent to. However, this is non-embeddable. Therefore every point must have at least three points not connected to it. This proves that f(7)=4. Now to prove that f(8)=4.

Edit: Unfortunately, this appears to be a lot harder than I first thought. I found a 9 point graph with a point A that is connected to all but three points, and those three points are in a triangle, and adjacent to four other points each. The only thing that is not satisfied is that the points that A is adjacent to do not have 4 adjacent points, they only have two, so a proof would have to use the vertices that A is adjacent to.

[tomtom2357]

What if we included only the plane-embeddable graphs with no triangles, and tried to find the maximum chromatic number of that. It is obviously at least 3, because of the pentagon, but is it exactly 3? Any plane-embeddable graph with no triangle with chromatic number 4 must have at least 7 vertices (I stated a stronger version if this in an earlier post), and it must have an odd cycle (in other words it has a 2n+1-gon as a subgraph), otherwise the chromatic number is 2. In a minimal non-3-colorable graph, each point must be connected to at least 3 points.

[tomtom2357]

Did you post in the wrong thread?

[dudiobugtron]

Did you post in the wrong thread?

Yes, it should have posted in the "I'm a spammer, please delete this post" thread.

[Desiato]

6 year bump, but there's an update: It seems agreed upon now that the chromatic number of the plane is at least 5. Paper proving this can be found here(and googling shows many references to it with non doubting the result).