6-coloring a degree 5 graph

[Tom Sirgedas]

Here I plan to explore 6-color plane tilings for degree 5 graphs (and hopefully beyond, but it'll be easier to get traction this way).

I'm interested in discovering constraints that might be useful for proving that a 6-color plane tiling is impossible.

[Tom Sirgedas]

Here's a nice 6-color tiling from Gibbs that covers a disk with radius ~2.1. On top is the dual graph (ignore the white arrows). What properties does the dual graph have? One interesting thing to note is that all the interior vertices have degree 5. Degree 6 isn't possible with only 6 colors.

Here's a degree 5 graph (for interior vertices). This graph isn't viable because the tiles in the outer vertices would be too large. But how can this be mathematically stated and analyzed?

Here's another degree 5 graph where the tiles are more uniformly sized. I think this will be a useful example to test ideas on.

[Tom Sirgedas]

 

some degree 5 graphs with a regular pattern

[Tom Sirgedas]

can these graphs be 6-colored? no.

Showing this is pretty simple. Here we color a vertex red. Each neighbor must be a unique color.

Then an orange vertex and a purple vertex is forced (other colors are too close -- no vertex can have two same-color neighbors).

Then 4 more vertices are similarly forced (2 blue and 2 yellow). Finally, neither of the indicated vertices can be colored.

This also shows that no valid 6-color tiling can have this subgraph.

[Tom Sirgedas]

 

When the dual graph has a quadrilateral (or pentagon or hexagon), a curved edge is typically required in the graph. You can see in the curved edge in the example above. The white arrow on the dual graph also indicates a curved edge. (And I'll say that the central vertex "emits" a curved edge.)

With a degree 5 graph, this scenario will happen at each vertex of every quadrilateral (since every vertex has a neighbor for each color).

For this graph, you can see that each vertex will emit 2 curved edges, because every vertex is incident to 2 quadrilaterals. Note that the emitted curved edges must all be unique (the curve lies on a unit radius circle centered on the emitting vertex).

For the above graph, 80% of all edges will be forced to curve in this way. This will be true for all graphs consisting of only triangles and quads. (Intuitively, pentagons are even "worse", as each vertex of a pentagon emits 2 curved edges).

I think the high density of curved edges required will be a useful contraint.

[Tom Sirgedas]

Consider the quad indicated by the thin green rectangle above. It is emitting 4 curved edges (and the quad above it is emitting 2 as well). Now look at the corresponding graph on the right. Notices that the curved edges also mean that certain edges or diagonals (EDs) must be exactly unit length (rigid EDs -- indicated by black line segments). The quad in the dual graph corresponds to a vertex in the graph. This vertex is incident to 7 rigid EDs.

Every degree-4 vertex in the graph will be incident to rigid EDs in every direction. It seems that the average polygon in the graph will have at least two rigid EDs. This will tend to keep the tiles in the graph roughly the same size, and prevent "goofy" topology -- for example, if the blank tiles were removed, intuitively, you couldn't add a tile that touched both the central red and central blue tiles above. I'm not sure how to make this precise though. (But first, we'll try to make a "proof" that's intuitively true, and worry about being precise later).

[Tom Sirgedas]

Here's an interesting way to show the "random" graph can't be 6-colored.

We pick a vertex (the red one) and all vertices connected to it in 2 steps or less, and focus only on that subgraph. The neighbors of the red vertex can be arbitrarily colored. Note that none of the 12 uncolored vertices can be red. Since 5 colors need to cover 12 vertices, at least one color must be used at least 3 more times. But, this can't be done.

Can the orange vertex be used three more times? The blacked-out vertices are too close. The remaining vertices can accommodate only 2 more orange vertices.

If you check the other colors, you'll see that none of them can be used 4 times in all.

This technique doesn't always work. Here there are 11 vertices for the 5 colors, but orange can successfully color 3 of the 11.

[Tom Sirgedas]

Here's an even simpler proof that the random graph can't be colored

Cover rule: For a degree-5 6-colored graph, every vertex must "cover" each color. (e.g. each vertex must either be red or have a red neighbor). Proof: otherwise there's a duplicate color among those 6 vertices.

Above, vertex 5 must either be red, or have a red neighbor. Only vertex 6 is far enough from vertex 29, so it must be red.

But now vertex 1 can't be covered.

That's it!

[Aubrey de Grey]

Nice! Are you making progress in extending random graphs to all graphs?

[Tom Sirgedas]

Well, I haven't used anything actually random. I'm just calling the big amorphous example graph the "random" graph.

Not much progress, even for the degree-5 graphs, but I feel like proving it impossible should be within reach with a clever idea or two.

Maybe I'll try just enumerating degree-5 planar graphs and see if they can all be proved uncolorable. I'm not totally sure that's useful by itself. I feel like I need another insight that provides a shortcut.

[Tom Sirgedas]

For 6-colored degree 5 graph with only triangles & quads:

This graph

must be extended like this:

Proof:

If we add a quad instead, then neither red edge can have a triangle attached.

But, attaching two quads instead also fails. (2 colors are forced to cover the 4 highlighted vertices, which can't be done)

On Saturday, October 17, 2020 at 12:58:49 PM UTC-4 Tom Sirgedas wrote:

For 6-colored degree 5 graph with only triangles & quads:

This graph

must be extended like this:

Proof:

If we add a quad instead, then neither red edge can have a triangle attached.

But, attaching two quads instead also fails. (2 colors are forced to cover the 4 highlighted vertices, which can't be done)

[Tom Sirgedas]

Hmm, trying to prove this graph doesn't work isn't simple. It can grow pretty large and still be valid.

My old searcher finds ~4000 graphs before deciding that it's impossible. Here's one of the large graphs it found:
  

(I circled the original graph)

For this graph, it looks like the right-most green tile was added last and the graph can't be further expanded near that tile. We can probably eliminate a lot of the ~4000 graphs from the "proof" by building towards that green tile more directly. Well, I was hoping to generate a more hand-crafted proof using just a few graphs, but that didn't work out.

Also, these large graphs are impossibly hopeless in the simulator. But, studying them shows that it's important to find/invoke rules beyond what I have currently implemented. This large graph is invalid, but how can you know this without using the simulator? Without an answer, large graphs like this can't be easily discarded.

[Tom Sirgedas]

So here's a sub graph of the large graph. The simulator and searcher like it, but there are a lot of curved edges that don't work. For example, the white arrow above travels through 1 unit distance over the yellow tile, plus at least one more unit distance to get to the yellow-green-purple vertex. So the arrow must be at least 2 units in length. However, there are two rigid EDs that cover that same distance, which is impossible. So, the two yellow tiles are actually too close to each other. I think proving this might need to involve the larger structure formed by all the rigid EDs together (??). Not sure. But that's discouraging. It's not essential to prove that this graph is invalid, because you can't add to it indefinitely. But I'm not interested in enumerating those additions.

[Tom Sirgedas]

80% of edges in an infinite 6-colored degree-5 graph will be curved. The curved edges in the graph above are marked with a white arrow.

It's interesting to note that the last vertex (the right-most green vertex) is "saturated" with curved edges. Intuitively, I think it's these curved edges that stunt the further growth of the graph. Maybe it can be shown that as you expand the graph outwards, each layer adds slightly more curved edges (?) until a local failure is guaranteed(?)

[Aubrey de Grey]

Yeah, I agree, this is not looking good. I think the key to a hand-crafted proof must be to find a few small graphs that are impossible and then exclude them from appearing in the expansions of other graphs - but what those initial small graphs are, I have no idea.

[Tom Sirgedas]

definition of "tile distance": the shortest number of steps between two tiles, where each step takes you to another tile by crossing an edge.

Note that two red tiles must have "tile distance" at least 3.


This might be a useful concept: a "metagraph".

Given a tiling, a red "metagraph" is a graph(V, E), with V = set of red tiles, and E = pairs of red tiles with "tile distance" 3.


Can a "metagraph" have crossing edges like this?

No!  Proof: connect one diagonal via 2 tiles (tiles are vertices in the image above). The other diagonal can't be formed, because the diagonals must cross at a vertex, making two red vertices too close together.

So, the metagraph must be planar.

On Saturday, December 5, 2020 at 3:58:00 PM UTC-5 Tom Sirgedas wrote:

definition of "tile distance": the shortest number of steps between two tiles, where each step takes you to another tile by crossing an edge.

Note that two red tiles must have "tile distance" at least 3.



This might be a useful concept: a "metagraph".

Given a tiling, a red "metagraph" is a graph(V, E), with V = set of red tiles, and E = pairs of red tiles with "tile distance" 3.


Can a "metagraph" have crossing edges like this?

No!  Proof: connect one diagonal via 2 tiles (tiles are vertices in the image above). The other diagonal can't be formed, because the diagonals must cross at a vertex, making two red vertices too close together.

So, the metagraph must be planar.

[Tom Sirgedas]

more on metagraphs...

OK, here's an example graph with a red vertex. The cyan/white/black vertices just indicate a tile distance of 1/2/3 from the red vertex. 

Note that the cyan & white vertices can't be colored red.

For a degree 5 graph, all non-red vertices must have a red neighbor. So, all white vertices must have a red neighbor. Only the black vertices can be colored red. So, it's interesting to think about which black vertices to color red, and what this means for the red metagraph.

I think these are the only ways to choose the red vertices in the black layer (also, the first two can be vertically flipped). And often it's impossible on random graphs.

Anyways, notice that only the last graph doesn't form a closed shape with triangles. The red vertices are tile distance 4 apart.

Consider the 2 black vertices half-way between the "disconnected" red vertices. These both need an adjacent red vertex. These 2 new red vertices add 4 edges to the metagraph.

So, for a degree-5, 6-colored graph with only triangles&quads, I think the metagraph will be made of triangles and quads. I assume this is true, but I won't try to prove it until this result leads to a more interesting result.

Also, interesting to note this structure inside both of the metagraph's quads. I suspect that no other arrangement is possible (?).

[Tom Sirgedas]

  

Some extreme cases to consider. The metagraphs are still triangles&quads. The second graph's red metagraph has a ton of edges at the center (15).

[Tom Sirgedas]

[Tom Sirgedas]

Define a red "block" as a red tile and its neighbors.

Then, a 6-colored 5-regular graph that covers the plane can be partitioned into red blocks (example above)

The red blocks form the red metagraph. As shown earlier, this graph must be planar.

---

Also this graph can't have pentagons. Proof:



A pentagon in the red metagraph means that the boundaries of the 5 red blocks share a common point. So, exactly 5 tiles meet at this common point, using all 5 non-red colors.

Now consider the 5 tiles that meet at the boundary point. A red tile can't be adjacent to any two of these tiles (because this would mean that the two tiles were actually part of the same red block). 



So, another color must be used, causing the 5 tile edges emanating from the common point to be rigid.



The 5 rigid EDs have length 1, but then the "pentagon" will have at least one "edge" with length > 1.

[Tom Sirgedas]

Similarly the metagraph can't have a quadrilateral. (Well, I'm pretty certain, but the proof below is a bit sloppy(?)).

Proof by contradiction again: [incomplete, hand-wavy!]



If only 4 tiles meet at the common point, then we have 4 edges emanating from the common point. "Opposite" edges (left/right or top/bottom) can't both be rigid (because then at least one of the 4 tiles would need to have width > 1).


Consider the unit circle centered on the common point. Here yellow is the color without a unit-length emanating from the common point. Note that only red & orange can "pick up the slack" in the unit circle. However, the combined red/orange region will have width > 1 and this region can't actually be two-colored.

[Tom Sirgedas]

For the previous "proof", I think maybe considering only the thin ring of points that have distance [1-epsilon, 1+epsilon] from the common point would be helpful. And then noting that purple/green/blue/yellow portions (tiles) can't span arcs > 60 degrees.

Also, the proof needs to consider 5 tiles meeting at the common point, because one red block may contribute two tiles.

[Tom Sirgedas]

So, the red metagraph must have only triangles. This is a very nice restriction, but I'm not sure how to show that it's impossible. Gibbs' radius 2 graph has a red metagraph with 5 "meta"-triangles. It's good to keep this in mind when brainstorming proof ideas.

But I'm happy with these metagraph ideas because it allows proofs without relying on enumerating a ton of cases.

[Tom Sirgedas]

Here's a diagram showing the consequences of a quadrilateral including a red vertex. It might be an interesting building block when thinking of metagraphs.

[Tom Sirgedas]

The graph is infinite, but I'll say it has n vertices to make it easier to think about relative quantities.

The graph has n vertices.

Each vertex is incident to 5 edges, so that's 2.5n edges total.

Assuming the graph has only triangles and quadrilaterals, it has n triangles and .5n quads. This is to satisfy E=F+V:

#edges = #faces + #vertices

2.5n = (n + .5n) + n

1 quad "emits" 4 curved edges. This is 2n edges (80% of all edges).

On average, each vertex is incident to 3 triangles, 2 quads, 4 curved edges.

---

Now let's consider all length-1 and length-2 paths in the graph. Ignore paths that repeat a vertex.

n vertices
5n length-1 paths

20n length-2 paths (4 color choices to extend each length-1 path)

Let's figure out how many ordered pairs of vertices (a,b) there are, such that there's a path from a to b with length 1 or 2.

Each triangle in the graph contains 6 length-2 paths that are redundant. There are 6n of these redundant paths.
(For example, in triangle ABC, we can get from A to C using AB then BC, but we'll use AC instead).

Each square in the graph contains 4 corners, with two ways to reach the opposite corner in 2 steps. So 4n redundant paths.

Each pair of triangles in the graph that shares an edge has 2 more redundant paths. (ACD is redundant for ABD, and DCA is redundant for DBA. Note that paths from C to B and B to C were already marked as redundant). The graph will have at least .5n such triangle pairs and at most n. So [n, 2n] redundant paths.


So there are [9n, 10n] "redundant" paths total, out of 25n.
So, [15n, 16n] unique paths.

So on average each vertex has [15,16] vertices distance 1 or 2 away from it.
So on average each vertex has [10,11] vertices distance 1 or 2 away from it.

When a vertex has 11 vertices at length-2, then those 11 vertices have to be colored with only 5 colors. So, at least one color needs to appear 3 times, which is a difficult constraint. (For example, the 17 red/yellow/blue vertices in the left-side graph can't be 6-colored such that no vertex has 2 same-color neighbors.)

[Tom Sirgedas]

Gah, ignore the large image at the very start of the previous message.

[Aubrey de Grey]

Hey Tom - I emailed you recently about a possible future Zimmerman problem - did you get my mail? My new email address is aub...@levf.org or you can reach me at Twitter or LinkedIn.