1 citations · 1 across the 7 of their papers we have counts for
11 papers
The Price of Connectivity Augmentation on Planar Graphs
Hugo A. Akitaya, Justin Dallant, Erik D. Demaine +5
Given two classes of graphs, , and a -connected graph , we wish to augment with a smallest cardinality set of new e…
Odd coloring graphs with linear neighborhood complexity
James Davies, Meike Hatzel, Kolja Knauer +2
We prove that any class of graphs with linear neighborhood complexity has bounded improper odd chromatic number. As a result, if is the class of all circle graphs, or…
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.
Girth in -representable matroids
James Davies, Meike Hatzel, Kolja Knauer +2
We prove a conjecture of Geelen, Gerards, and Whittle that for any finite field and any integer , every cosimple -representable matroid with sufficiently large gi…
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 ,…
On the Relation Between Treewidth, Tree-Independence Number, and Tree-Chromatic Number of Graphs
Alex Koutsoutis, Kilian Krause, Chun-Hung Liu +2
We investigate two recently introduced graph parameters, both of which measure the complexity of the tree decompositions of a given graph. Recall that the treewidth o…
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…
Intersection Graphs with and without Product Structure
Laura Merker, Lena Scherzer, Samuel Schneider +1
A graph class admits product structure if there exists a constant such that every is a subgraph of for a path and some gra…
Transforming Stacks into Queues: Mixed and Separated Layouts of Graphs
Julia Katheder, Michael Kaufmann, Sergey Pupyrev +1
Some of the most important open problems for linear layouts of graphs ask for the relation between a graph's queue number and its stack number or mixed number. In such, we seek a v…
Partitioning a Planar Graph into two Triangle-Forests
Kolja Knauer, Clément Rambaud, Torsten Ueckerdt
We show that the vertices of every planar graph can be partitioned into two sets, each inducing a so-called triangle-forest, i.e., a graph with no cycles of length more than three.…
Polychromatic Colorings of Geometric Hypergraphs via Shallow Hitting Sets
Tim Planken, Torsten Ueckerdt
A range family is a family of subsets of , like all halfplanes, or all unit disks. Given a range family , we consider the -uniform range…