4 papers
Revisiting classical results on kernels in digraphs
Hélène Langlois, Frédéric Meunier
In a digraph, a kernel is a subset of vertices that is both independent and absorbing. Kernels have important applications in combinatorics and outside. Kernels do not always exist…
Quasi-kernels in split graphs
Hélène Langlois, Frédéric Meunier, Romeo Rizzi +2
In a digraph, a quasi-kernel is a subset of vertices that is independent and such that the shortest path from every vertex to this subset is of length at most two. The ``small quas…
Partitioning into degenerate graphs in linear time
Timothée Corsini, Quentin Deschamps, Carl Feghali +3
Let be a connected graph with maximum degree distinct from . Generalizing Brooks' Theorem, Borodin, Kostochka and Toft proved that if are…
Algorithmic aspects of quasi-kernels
Hélène Langlois, Frédéric Meunier, Romeo Rizzi +1
In a digraph, a quasi-kernel is a subset of vertices that is independent and such that every vertex can reach some vertex in that set via a directed path of length at most two. Whe…