Coloring Circle Arrangements: New 4-Chromatic Planar Graphs

Man Kwun Chiu, Stefan Felsner, Manfred Scheucher*, Felix Schröder, Raphael Steiner, Birgit Vogtenhuber

*Korrespondierende/r Autor/-in für diese Arbeit

Publikation: Beitrag in Buch/Bericht/KonferenzbandBeitrag in Buch/BerichtBegutachtung


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.

TitelTrends in Mathematics
Herausgeber (Verlag)Springer Science and Business Media Deutschland GmbH
PublikationsstatusVeröffentlicht - 2021


NameTrends in Mathematics
ISSN (Print)2297-0215
ISSN (elektronisch)2297-024X

ASJC Scopus subject areas

  • Mathematik (insg.)


Untersuchen Sie die Forschungsthemen von „Coloring Circle Arrangements: New 4-Chromatic Planar Graphs“. Zusammen bilden sie einen einzigartigen Fingerprint.

Dieses zitieren