Keywords

1 Introduction

An arrangement of pseudocircles is a family of simple closed curves on the sphere or in the plane such that each pair of curves intersects at most twice. Similarly, an arrangement of pseudolines is a family of x-monotone curves such that every pair of curves intersects exactly once. An arrangement is simple if no three pseudolines/pseudocircles intersect in a common point and intersecting if every pair of pseudolines/pseudocircles intersects. Given an arrangement of pseudolines/pseudocircles, the arrangement graph is the planar graph obtained by placing vertices at the intersection points of the arrangement and thereby subdividing the pseudolines/pseudocircles into edges.

A (proper) coloring of a graph assigns a color to each vertex such that no two adjacent vertices have the same color. The chromatic number \(\chi \) is the smallest number of colors needed for a proper coloring. The famous 4-color theorem and also Brook’s theorem imply the 4-colorability of planar graphs with maximum degree 4. This motivates the question: which arrangement graphs need 4 colors in any proper coloring?

Fig. 1.
figure 1

A 4-chromatic non-simple line arrangement. The red subarrangement not intersecting the Moser spindle (highlighted blue) can be chosen arbitrarly.

Full size image

There exist arbitrarily large non-simple line arrangements that require 4 colors. For example, the construction depicted in Fig. 1 contains the Moser spindle as a subgraph and hence cannot be 3-colored. Using an inverse central (gnomonic) projection, which maps lines to great-circles, one gets non-simple arrangements of great-circles with \(\chi = 4\). Koester [12] presented a simple arrangement of 7 circles with \(\chi =4\) in which all but one pair of circles intersect, see Fig. 3(c). Moreover, there are simple intersecting arrangements that require 4 colors. We invite the reader to verify this property for the example depicted in Fig. 2.

In 2000, Felsner, Hurtado, Noy and Streinu [3] (cf. [4]) studied arrangement graphs of pseudoline and pseudocircle arrangements. They have results regarding connectivity, Hamiltonicity, and colorability of those graphs. In this work, they also stated the following conjecture:

Conjecture 1

(Felsner et al. [3, 4]). The arrangement graph of every simple arrangement of great-circles is 3-colorable.

While the conjecture is fairly well known (cf. [10, 14, 18] and [19, Chapter 17.7]) there has been little progress in the last 20 years. Aichholzer, Aurenhammer, and Krasser verified the conjecture for up to 11 great-circles [13, Chapter 4.6.4].

Results and Outline. In Sect. 2 we show that Conjecture 1 holds for \(\triangle \)-saturated arrangements of pseudocircles, i.e., arrangements where one color class of the 2-coloring of faces consists of triangles only. In Sect. 3 we extend our study of \(\triangle \)-saturated arrangements and present an infinite family of arrangements which require 4 colors. The construction generalizes Koester’s [12] arrangement of 7 circles which requires 4 colors; see Fig. 3(c). Moreover, we believe that the construction results in infinitely many 4-vertex-criticalFootnote 1 arrangement graphs. Koester [12] obtained his example using a “crowning” operation, which actually yields infinite families of 4-edge-critical 4-regular planar graphs. However, except for the 7 circles example these graphs are not arrangement graphs.

Fig. 2.
figure 2

A simple intersecting arrangement of 5 pseudocircles with \(\chi =4\) and \(\chi _f=3\).

Full size image
Fig. 3.
figure 3

(a) A \(\triangle \)-saturated arrangement \(\mathcal {A}\) of 6 great-circles. (b) The doubling method applied to \(\mathcal {A}\). The red pseudocircle is replaced by a cyclic arrangement. Triangular cells are shaded gray. (c) The corona extension of \(\mathcal {A}\) at its central pentagonal face. This arrangement is Koester’s [11] example of a 4-edge-critical 4-regular planar graph.

Full size image

In Sect. 4 we investigate the fractional chromatic number \(\chi _f\) of arrangement graphs. This variant of the chromatic number is the objective value of the linear relaxation of the ILP formulation for the chromatic number. We show that intersecting arrangements of pseudocircles are “close” to being 3-colorable by proving that \(\chi _f(\mathcal {A}) \le 3+O(\frac{1}{n})\) where n is the number of pseudocircles of \(\mathcal {A}\). In Sect. 5, we present an example of a 4-edge-critical arrangement graph which is fractionally 3-colorable. The example is the basis for constructing an infinite family of 4-regular planar graphs which are 4-edge-critical and fractionally 3-colorable. This disproves Conjecture 3.2 from Gimbel, Kündgen, Li and Thomassen [7] that every 4-chromatic planar graph has fractional chromatic number strictly greater than 3. In Sect. 6 we report on our computational data, mention some some new observations related to Conjecture 1, and present strengthened versions of the conjecture.

Due to space constraints, some proofs are deferred to the full version of this work.

2 \(\triangle \)-Saturated Arrangements are 3-Colorable

The maximum number of triangles in arrangements of pseudolines and pseudocircles has been studied intensively, see e.g. [2, 8, 15] and [6]. By recursively applying the “doubling method”, Harborth [9] and also [2, 15] proved the existence of infinite families of \(\triangle \)-saturated arrangements of pseudolines. Similarly, a doubling construction for arrangements of (great-)pseudocircles yields infinitely many \(\triangle \)-saturated arrangements of (great-)pseudocircles. Figures 3(a) and 3(b) illustrate the doubling method applied to an arrangement of great-pseudocircles. It will be relevant later that arrangements obtained via doubling contain pentagonal cells. Note that for \(n \equiv 2 \pmod 3\) there is no \(\triangle \)-saturated intersecting pseudocircle arrangement because the number of edges of the arrangement graph is not divisible by 3.

Theorem 1

Every \(\triangle \)-saturated arrangement \(\mathcal {A}\) of pseudocircles is 3-colorable.

Proof

Let H be a graph whose vertices correspond to the triangles of \(\mathcal {A}\) and whose edges correspond to pairs of triangles sharing a vertex of \(\mathcal {A}\). This graph H is planar and 3-regular. Moreover, since the arrangement graph of \(\AA \) is 2-connected, H is bridgeless. Now Tait’s theorem, a well known equivalent of the 4-color theorem, asserts that H is 3-edge-colorable, see e.g. [1] or [17]. The edges of H correspond bijectively to the vertices of the arrangement \(\mathcal {A}\) and, since adjacent vertices of \(\mathcal {A}\) are incident to a common triangle, the corresponding edges of H share a vertex. This shows that the graph of \(\mathcal {A}\) is 3-colorable.

3 Constructing 4-Chromatic Arrangement Graphs

In this section, we describe an operation that extends any \(\triangle \)-saturated intersecting arrangement of pseudocircles with a pentagonal cell (which is 3-colorable by Theorem 1) to a 4-chromatic arrangement of pseudocircles by inserting one additional pseudocircle.

The Corona Extension: We start with a \(\triangle \)-saturated arrangement of pseudocircles which contains a pentagonal cell . By definition, in the 2-coloring of the faces one of the two color classes consists of triangles only; see e.g. the arrangement from Fig. 3(a). Since the arrangement is \(\triangle \)-saturated, the pentagonal cell is surrounded by triangular cells. As illustrated in Fig. 3(c) we can now insert an additional pseudocircle close to . This newly inserted pseudocircle intersects only the 5 pseudocircles which bound , and in the so-obtained arrangement one of the two dual color classes consists of triangles plus the pentagon . It is interesting to note that the arrangement depicted in Fig. 3(c) is precisely Koester’s arrangement [11, 12].

The following proposition plays a central role in this section.

Proposition 1

The corona extension of a \(\triangle \)-saturated arrangement of pseudocircles with a pentagonal cell  is 4-chromatic.

The proof is based on the observation that after the corona extension the inequality \(3\alpha < |V|\) holds.

By applying the corona extension to members of the infinite family of \(\triangle \)-saturated arrangements with pentagonal cells (cf. Sect. 2), we obtain an infinite family of arrangements that are not 3-colorable.

Theorem 2

There exists an infinite family of 4-chromatic arrangements of pseudocircles.

Koester [12] defines a related construction which he calls crowning and constructs his example by two-fold crowning of a graph on 10 vertices. He also uses crowning to generate an infinite family of 4-edge-critical 4-regular graphs. In the full version of our paper, we present sufficient conditions to obtain a 4-vertex-critical arrangement via the corona extension. We conclude this section with the following conjecture:

Conjecture 2

There exists an infinite family of arrangement graphs of arrangements of pseudocircles that are 4-vertex-critical.

4 Fractional Colorings

In this section, we investigate fractional colorings of arrangements. A b-fold coloring of a graph G with m colors is an assignment of a set of b colors from \(\{1,\ldots ,m\}\) to each vertex of G such that the color sets of any two adjacent vertices are disjoint. The b-fold chromatic number \(\chi _b(G)\) is the minimum m such that G admits a b-fold coloring with m colors. The fractional chromatic number of G is \(\chi _f(G) := {\displaystyle \lim _{b \rightarrow \infty }}\frac{\chi _b(G)}{b} = {\displaystyle \inf _{b}} \frac{\chi _b(G)}{b}\). With \(\alpha \) being the independence number and \(\omega \) being the clique number, it holds that:

$$\begin{aligned} \max \left\{ \frac{|V|}{\alpha (G)},\omega (G) \right\} \le \chi _f(G) \le \frac{\chi _b(G)}{b} \le \chi (G). \end{aligned}$$
(1)

Theorem 3

Let G be the arrangement graph of an intersecting arrangement \(\mathcal {A}\) of n pseudocircles, then \(\chi _f (G)\le 3+\frac{6}{n-2}\).

Fig. 4.
figure 4

(a) A 4-edge-critical 4-regular 18-vertex planar graph with \(\chi \! =\! 4\) and \(\chi _f \!=\! 3\). and (b) the crowning extension at its center triangular face.

Full size image

Proof

(Sketch of the proof). Let C be a pseudocircle of \(\mathcal {A}\). After removing all vertices along C from the arrangement graph G we obtain a graph which has two connected components A (vertices in the interior of C) and B (vertices in the exterior). Let \(C'\) be a small circle contained in one of the faces of A, the Sweeping Lemma of Snoeyink and Hershberger [16] asserts that there is a continuous transformation of \(C'\) into C which traverses each vertex of A precisely once. In particular, when a vertex is traversed, at most two of its neighbors have been traversed before. Hence, we obtain a 3-coloring of the vertices of A by greedily coloring vertices in the order in which they occur during the sweep. An analogous argument applies to B. Taking such a partial 3-coloring of G for each of the n pseudocircles of \(\mathcal {A}\), we obtain for each vertex a set of \(n-2\) colors, i.e., an \((n-2)\)-fold coloring of G. The total number of colors used is 3n. The statement now follows from inequality (1).

5 Fractionally 3-Colorable 4-Edge-Critical Planar Graphs

From our computational data (cf. [5]), we observed that some of the arrangements such as the 20 vertex graph depicted in Fig. 2 have \(\chi =4\) and \(\chi _f=3\), and therefore disprove Conjecture 3.2 by Gimbel et al. [7]. Moreover, we determined that there are precisely 17 4-regular 18-vertex planar graphs with \(\chi =4\) and \(\chi _f=3\), which are minimal in the sense that there are no 4-regular graphs on \(n \le 17\) vertices with \(\chi =4\) and \(\chi _f=3\). Each of these 17 graphs is 4-vertex-critical and the one depicted in Fig. 4(a) is even 4-edge-critical.

Starting with a triangular face in the 4-edge-critical 4-regular graph depicted in Fig. 4(a) and repeatedly applying the Koester’s crowning operation [12] as illustrated in Fig. 4(b) (which by definition preserves the existence of a facial triangle), we deduce the following theorem.

Theorem 4

There exists an infinite family of 4-edge-critical 4-regular planar graphs G with fractional chromatic number \(\chi _f(G)=3\).

6 Discussion

With Theorem 1 we confirmed Conjecture 1 for \(\triangle \)-saturated great-pseudocircle arrangements. While this is a very small subclass of great-pseudocircle arrangements, it is reasonable to think of it as a “hard” class for 3-coloring. The rationale for such thoughts is that triangles restrict the freedom of extending partial colorings. Our computational data indicates that sufficiently large intersecting pseudocircle arrangements that are diamond-free, i.e., no two triangles of the arrangement share an edge, are also 3-colorable. Computations also suggest that sufficiently large great-pseudocircle arrangements have antipodal colorings, i.e., 3-colorings where antipodal points have the same color. Based on the experimental data we propose the following strengthened variants of Conjecture 1.

Conjecture 3

The following three statements hold.

  1. (a)

    Every diamond-free intersecting arrangement of \( n \ge 6 \) pseudocircles is 3-colorable.

  2. (b)

    Every intersecting arrangement of sufficiently many pseudocircles is 3-colorable.

  3. (c)

    Every arrangement of \(n \ge 7\) great-pseudocircles has an antipodal 3-coloring.