## Coloring Problems for Arrangements of Circles (and Pseudocircles)

To supplement and celebrate Aubrey de Grey’s result here are

## Eight problems on coloring circles

A) Consider a finite family of unit circles. What is the minimum number of colors needed to color the circles so that tangent circles are colored with different colors?

This is the question about the chromatic number of the plane. (Or the maximum chromatic number of planar unit-distance graphs.) By the Aubrey de Grey’s result the answer is 5, 6, or 7.

B) Consider a finite family of non-overlapping unit circles. What is the minimum number of colors needed to color the circles so that tangent circles are colored with different colors?

Now we talk about planar unit-distance graphs where the distance between every pair of points is at least one. Those are also called Penny graphs. The answer is four.

C) Consider a finite family of pairwise intersecting unit circles. What is the minimum number of colors needed to color the circles so that tangent circles are colored with different colors?

This is a the (finite) planar Borsuk problem. (Now we talk about planar unit-distance graphs where the distance between every pair of points is at most one.) The answer is 3, and this follows from a simple characterization these graphs.

D) Consider a finite family of non-overlapping circles. What is the minimum number of colors needed to color the circles so that tangent circles are colored with different colors?

By Koebe’s circle packing theorem (see this recent post) this is precisely the four color theorem so the answer is 4.

E) Consider a finite family of  circles. What is the minimum number of colors needed to color the circles so that tangent circles are colored with different colors?

Unless we make some further assumption the answer is infinite. Rom Pinchasi proved that $\log ^2 n$ collors suffice and also  gave an example of $n$ circles where the chromatic number is at least $c\log n$.

F) Consider a finite family of  circles such that every point in the plane is included in at most two circles.  What is the minimum number of colors needed to color the circles so that tangent circles are colored with different colors?

Ringel’s circle conjecture (see this paper by Jackson and Ringel) asserts that the number of colors is bounded. (There is an example that five colors are required.)

G) Consider a finite family of pairwise intersecting circles. What is the minimum number of colors needed to color the circles so that tangent circles are colored with different colors?

H) Consider a finite family of  pseudocircles.  Here every pseudocircle is a closed simple path and two pseudocicles are either disjoint or hace two crossing points. Two pseudocircles are adjacent if the lens described by them does not contain any point from any other pseudocircle. What is the minimum number of colors needed to color the pseudocircles so that adjacent pseudocircles are colored with different colors? (In particular, is this number finite?)

## Remarks

### Number of edges and other properties

Each of the above questions give rise to a family of graphs and lead to other interesting questions about these graphs. For example, we can ask what is the maximal number of edges in each case.

For unit distance graphs (question A) this is the famous  Erdős unit distance problem. (Here is a survey by Szemeredi).

The Maximum number of edges of Borsuk planar graphs (question C) is $n$ (see this proof using lice), and this immediately implies that their chromatic number is at most three.

The maximum number of edges of Penny graphs (question B) is known and there is an intruiging conjecture for triangle free Penny graphs.

The maximum number of edges of (simple) planar graphs (question D) $3n-6$ as follows easily from Euler’s theorem.

Alon, Last, Pinchasi, and Sharir  showed an upper bound of $2n-2$ for the number of edges in the tangent graph for pairwise intersecting circles. (Question G.)

An intruiging conjecture by Pinchasi, Sharir, and others is that planar tangent graphs (Question E) with $n$ vertices can have at most $n^{4/3}polylog(n)$ edges. This conjecture proposes a profound extension of the Szemeredi–Trotter theorem. The best known upper bound $n^{3/2}\log n$ is by Marcus and Tardos.

### Sylvester-Gallai type results

For circles that pairwise intersect, Rom Pinchasi proved a Gallai–Sylvester conjecture by Bezdek asserting that (for more than 5 circles) there is always a circle tangential to at most two other circles. This was the starting point of important studies  concerning arrangement of circles and pseudo-circles in the plane.

### High dimensions

Each of the above questions extends to higher dimensions and also here they include some well known problems. It is a famous result by Frankl and Wilson that the cromatic number of $\mathbb R^d$ is exponential in $d$. We now know (see this post) that there are $d$-dimensional “hyper-penny” graphs with minimal degree that is exponential in $d$. Is the chromatic number of such graphs can also be exponential in $d$?

## When you ask these questions without stress. (Adding the strong Arnold property).

A stress (affine stress to be precise) of a geometric graph is an assignement of weights to edges so that every vertex is in equilibrium. We can ask many of the problems above (e.g. see this post) when we assume that the graph is stress-free, namely does not admit non-trivial stresses. (When we consider circles of different sizes we probably need to consider stresses in three dimensions.) We can think about stress-freeness as saying that we have a “non coincidental” configuration.

This entry was posted in Combinatorics, Geometry, Open problems and tagged , , . Bookmark the permalink.

### 12 Responses to Coloring Problems for Arrangements of Circles (and Pseudocircles)

1. Stan Wagon says:

A favorite coloring problem of many (unsolved) is this: Consider the graph made from some set of great circles on a sphere, with no three meeting at a point. Vertices are the intersection points; edges the connecting arcs. Is such a graph always 3-colorable? A YES answer seems reasonable and I have coded the problem and checked 100s of random examples. Kempe chains seem like a way to approach it. I can prove that the graph, when restricted to the northern hemisphere plus the equator is 3-colorable. But not clear how to handle both north and south together

• Gil Kalai says:

Dear Stan, very nice problem. Do you have some link for further information?

• Stan Wagon says:

A place to start is
S. Felsner, F. Hurtado, M. Noy, and I. Streinu, Hamiltonicity and coloring properties of arrangement graphs, in Proc. Symp. on Disc. Algorithms, ACM Press (2000) 655\[Dash]664.

Also my book, Mathematica in Action, Chap 17, (3rd ed.) has a section on it, including code I wrote to generate and display the properly 3-colored graphs on spheres.

I made the conjecture myself, then found that it was made in the paper above. It has several equivalent formulations. Eg: Take a map on the sphere in which every country is a spherical parallelogram. Then that map is 3-colorable as a set of countries. I might have some detail wrong here. There is a name for these sorts of maps on spheres, but it eludes me.

2. Stan Wagon says:

I remembered: The problem is directly equivalent to: EVERY ZONOHEDRON IS 3-COLORABLE. That is the form I discovered. That in turn arose from something involving Penrose tilings in the plane (they too are 3-colorable!). Again, in this context it is the MAP that is being 3-colored.

3. Gil Kalai says:

Many thanks, Stan. Greg Kuperberg noted on Shtetl Optimized that the Hadwiger-Nelson problem is interesting in the hyperbolic plane and I suppose this extends to many of the problems we discuss here.

• Konstantin Golubev says:

Hi Gil,

I was searching the web for recent results on the Hadwiger-Nelson problem on the hyperbolic plane and came across this comment of yours. So I thought it might be of interest to you.

Unlike the Euclidean plane, the question on the hyperbolic depends on the distance. As far as I know, the current state of the results is as follows:

A linear upper bound proved by Kloeckner and improved by Perlier and Petit.

A constant lower bound of 6 proved by Evan DeCorte and myself.

If the coloring is conditioned to be periodic (equivalently, the chromatic number of a hyperbolic surface), the chromatic number is bounded both from above and below by exponential functions. The upper bound is a variant of the Brooks bound for finite graphs and proved by Perlier and Petit. The lower bound appears in the recent paper of mine.

Best,
Kostâ

• Gil Kalai says:

Dear Kostâ, many thanks for the very interesting information and links!

4. bjonas says:

I think you have made a mistake describing question D. What does \$n\$ mean? If you have no restrictions, then all pairs of circles can be tangent, by fixing a line and a point on it, and choosing all circles tangent to the line in the point.

• Gil Kalai says:

Good point. By tangent we mean two circles which are separated by their common tangent.

5. Gil Kalai says:

Here is a videotaped lecture about these questions