Coloring circle arrangements: New 4-chromatic planar graphs
METADATA ONLY
Loading...
Author / Producer
Date
2024-10
Publication Type
Journal Article
ETH Bibliography
yes
Citations
Altmetric
METADATA ONLY
Data
Rights / License
Abstract
Felsner, Hurtado, Noy and Streinu (2000) conjectured that arrangement graphs of simple great-circle arrangements have chromatic number at most 3. Motivated by this conjecture, we study the colorability of arrangement graphs for different classes of (pseudo-)circle arrangements. In this paper the conjecture is verified for -saturated pseudocircle arrangements, i.e., for arrangements where one color class of the 2-coloring of faces consists of triangles only, as well as for further classes of (pseudo-)circle arrangements. These results are complemented by a construction which maps -saturated arrangements with a pentagonal face to arrangements with 4-chromatic 4-regular arrangement graphs. This corona construction has similarities with the crowning construction introduced by Koester (1985). Based on exhaustive experiments with small arrangements we propose three strengthenings of the original conjecture. We further investigate fractional colorings. It is shown that the arrangement graph of every arrangement of pairwise intersecting pseudocircles is “close” to being 3-colorable. More precisely, the fractional chromatic number of the arrangement graph is bounded from above by , where is the number of pseudocircles of . Furthermore, we construct an infinite family of 4-edge-critical 4-regular planar graphs which are fractionally 3-colorable. This disproves a conjecture of Gimbel, Kündgen, Li, and Thomassen (2019).
Permanent link
Publication status
published
External links
Editor
Book title
Journal / series
Volume
121
Pages / Article No.
103839
Publisher
Elsevier
Event
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
Organisational unit
03672 - Steger, Angelika (emeritus) / Steger, Angelika (emeritus)