Coloring Circle Arrangements: New 4-Chromatic Planar Graphs

Felsner, Hurtado, Noy and Streinu (2000) conjectured that arrangement graphs of simple great-circle arrangements have chromatic number at most 3. This paper is motivated by the conjecture. We show that the conjecture holds in the special case when the arrangement is ▵ -saturated, i.e., arrangements where one color class of the 2-coloring of faces consists of triangles only. Moreover, we extend ▵ -saturated arrangements with certain properties to a family of arrangements which are 4-chromatic. The construction has similarities with Koester’s (1985) crowning construction. We also investigate fractional colorings. We show that every arrangement A of pairwise intersecting pseudocircles is “close” to being 3-colorable; more precisely χf(A)≤3+O(1n) where n is the number of pseudocircles. Furthermore, we construct an infinite family of 4-edge-critical 4-regular planar graphs which are fractionally 3-colorable. This disproves the conjecture of Gimbel, Kündgen, Li and Thomassen (2019) that every 4-chromatic planar graph has fractional chromatic number strictly greater than 3.