7 citations · 44 across the 35 of their papers we have counts for
6 papers · 1 filter
Majority Colorings of Sparse Digraphs
Michael Anastos, Ander Lamaison, Raphael Steiner +1
A majority coloring of a directed graph is a vertex-coloring in which every vertex has the same color as at most half of its out-neighbors. Kreutzer, Oum, Seymour, van der Zypen an…
On the Average Complexity of the -Level
Man-Kwun Chiu, Stefan Felsner, Manfred Scheucher +3
Let be an arrangement of lines in the Euclidean plane. The \emph{-level} of consists of all vertices of the arrangement which have exactly line…
A Note on Graphs of Dichromatic Number 2
Raphael Steiner
Neumann-Lara and Škrekovski conjectured that every planar digraph is -colourable. We show that this conjecture is equivalent to the more general statement that all oriented $K_5…
Complete Acyclic Colorings
Stefan Felsner, Winfried Hochstättler, Kolja Knauer +1
We study two parameters that arise from the dichromatic number and the vertex-arboricity in the same way that the achromatic number comes from the chromatic number. The adichromati…
Colouring Non-Even Digraphs
Marcelo Garlet Millani, Raphael Steiner, Sebastian Wiederrecht
A colouring of a digraph as defined by Erdos and Neumann-Lara in 1980 is a vertex-colouring such that no monochromatic directed cycles exist. The minimal number of colours required…
Flip distances between graph orientations
Oswin Aichholzer, Jean Cardinal, Tony Huynh +4
Flip graphs are a ubiquitous class of graphs, which encode relations induced on a set of combinatorial objects by elementary, local changes. Skeletons of associahedra, for instance…