13 citations · 14 across the 10 of their papers we have counts for
7 papers · 1 filter
A polynomial bound on the pathwidth of graphs edge-coverable by shortest paths
Julien Baste, Lucas De Meyer, Ugo Giocanti +2
Dumas, Foucaud, Perez and Todinca (2024) recently proved that every graph whose edges can be covered by shortest paths has pathwidth at most . In this paper, we improve…
Acyclic matchings in graphs of bounded maximum degree
Julien Baste, Maximilian Fürst, Dieter Rautenbach
A matching in a graph is acyclic if the subgraph of induced by the set of vertices that are incident to an edge in is a forest. We prove that every graph with v…
Domination versus edge domination
Julien Baste, Maximilian Fürst, Michael A. Henning +2
We propose the conjecture that the domination number of a -regular graph with is always at most its edge domination number , which coincides with th…
Bounding and approximating minimum maximal matchings in regular graphs
Julien Baste, Maximilian Fürst, Michael A. Henning +2
The edge domination number of a graph is the minimum size of a maximal matching in . It is well known that this parameter is computationally very hard, and several…
Linear programming based approximation for unweighted induced matchings --- breaking the barrier
Julien Baste, Maximilian Fürst, Dieter Rautenbach
A matching in a graph is induced if no two of its edges are joined by an edge, and finding a large induced matching is a very hard problem. Lin et al. (Approximating weighted induc…
Degenerate Matchings and Edge Colorings
Julien Baste, Dieter Rautenbach
A matching in a graph is -degenerate if the subgraph of induced by the set of vertices incident with an edge in is -degenerate. Goddard, Hedetniemi, Hedetniem…