BZPEER
More

Discover

About BZPEERSearchGraph

Research tools

HomeCollectionsResearchCollaborationPublish

Network

ExpertsCommunities

Opportunities

Listings

Account

Log inCreate account
Log inCreate account

Source author record

Felix Schröder

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record
Discrete Mathematicsmath.COComputational Geometry

Catalog footprint

Research overview

2works
3topics
4close collaborators

Actions

Is this your work?

Log in to claim
Open graphBrowse papers

Published work

2 publications

preprint2022arXiv

Coloring circle arrangements: New 44-chromatic planar graphs

Felsner, Hurtado, Noy and Streinu (2000) conjectured that arrangement graphs of simple great-circle arrangements have chromatic number at most 33. Motivated by this conjecture, we study the colorability of arrangement graphs for different classes of arrangements of (pseudo-)circles. In this paper the conjecture is verified for △\triangle-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 △\triangle-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 also investigate fractional colorings. It is shown that the arrangement graph of every arrangement A\mathcal{A} of pairwise intersecting pseudocircles is "close" to being 33-colorable. More precisely, the fractional chromatic number χf(A)χ_f(\mathcal{A}) of the arrangement graph is bounded from above by χf(A)≤3+O(1n)χ_f(\mathcal{A}) \le 3+O(\frac{1}{n}), where nn is the number of pseudocircles of A\mathcal{A}. Furthermore, we construct an infinite family of 44-edge-critical 44-regular planar graphs which are fractionally 33-colorable. This disproves a conjecture of Gimbel, Kündgen, Li, and Thomassen (2019).

Open access
preprint2022arXiv

Coloring Drawings of Graphs

We consider cell colorings of drawings of graphs in the plane. Given a multi-graph GG together with a drawing Γ(G)Γ(G) in the plane with only finitely many crossings, we define a cell kk-coloring of Γ(G)Γ(G) to be a coloring of the maximal connected regions of the drawing, the cells, with kk colors such that adjacent cells have different colors. By the 44-color theorem, every drawing of a bridgeless graph has a cell 44-coloring. A drawing of a graph is cell 22-colorable if and only if the underlying graph is Eulerian. We show that every graph without degree 1 vertices admits a cell 33-colorable drawing. This leads to the natural question which abstract graphs have the property that each of their drawings has a cell 33-coloring. We say that such a graph is universally cell 33-colorable. We show that every 44-edge-connected graph and every graph admitting a nowhere-zero 33-flow is universally cell 33-colorable. We also discuss circumstances under which universal cell 33-colorability guarantees the existence of a nowhere-zero 33-flow. On the negative side, we present an infinite family of universally cell 33-colorable graphs without a nowhere-zero 33-flow. On the positive side, we formulate a conjecture which has a surprising relation to a famous open problem by Tutte known as the 33-flow-conjecture. We prove our conjecture for subcubic and for K3,3K_{3,3}-minor-free graphs.

Open access

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.