2 papers
math.CO2019
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…
cs.DS2018
Efficient Algorithms for Measuring the Funnel-likeness of DAGs
Marcelo Garlet Millani, Hendrik Molter, Rolf Niedermeier +1
Funnels are a new natural subclass of DAGs. Intuitively, a DAG is a funnel if every source-sink path can be uniquely identified by one of its arcs. Funnels are an analog to trees f…