10 papers
Boundedness and Separation Between Induced and Non-Induced Covering Numbers
Miriam Goetze, Yidi Zang
There are four covering numbers , each of which measures in…
On t-colorable k-plane drawings
Miriam Goetze, Michael Kaufmann, Soeren Terziadis
In this work, we introduce -colorable -plane drawings, that is, drawings of graphs with a -edge-coloring where every edge is crossed by at most edges of each color. We…
On the Computational Complexity of Local and Global Covering Numbers
Miriam Goetze, Lucas Schwebler
The global and local -covering number and encode how well the edges of a graph can be covered w…
Strong odd coloring in minor-closed classes
Miriam Goetze, Fabian Klute, Kolja Knauer +3
We show that the strong odd chromatic number on any proper minor-closed graph class is bounded by a constant. We almost determine the smallest such constant for outerplanar graphs.
Boundedness and Separation in the Graph Covering Number Framework
Miriam Goetze, Peter Stumpf, Torsten Ueckerdt
For a graph class and a graph , the four -covering numbers of , namely global , union ,…
Crossing Number of 3-Plane Drawings
Miriam Goetze, Michael Hoffmann, Ignaz Rutter +1
We study 3-plane drawings, that is, drawings of graphs in which every edge has at most three crossings. We show how the recently developed Density Formula for topological drawings…
Saturated Drawings of Geometric Thickness k
Patricia Bachmann, Anna Brötzner, Miriam Goetze +3
We investigate saturated geometric drawings of graphs with geometric thickness , where no edge can be added without increasing . We establish lower and upper bounds on the nu…
The r-Dynamic Chromatic Number is Bounded in the Strong 2-Coloring Number
Miriam Goetze, Torsten Ueckerdt
A proper vertex-coloring of a graph is -dynamic if the neighbors of each vertex receive at least different colors. In this note, we prove that if…
Recognition Complexity of Subgraphs of k-Connected Planar Cubic Graphs
Miriam Goetze, Paul Jungeblut, Torsten Ueckerdt
We study the recognition complexity of subgraphs of k-connected planar cubic graphs for k = 1, 2, 3. We present polynomial-time algorithms to recognize subgraphs of 1- and 2-connec…
Efficient Recognition of Subgraphs of Planar Cubic Bridgeless Graphs
Miriam Goetze, Paul Jungeblut, Torsten Ueckerdt
It follows from the work of Tait and the Four-Color-Theorem that a planar cubic graph is 3-edge-colorable if and only if it contains no bridge. We consider the question of which pl…