8 citations · 51 across the 26 of their papers we have counts for
7 papers · 1 filter
Long cycles through prescribed vertices have the Erdős-Pósa property
Henning Bruhn, Felix Joos, Oliver Schaudt
We prove that for every graph, any vertex subset , and given integers : there are disjoint cycles of length at least that each contain at least one vertex fro…
Squares of -sun-free split graphs
Van Bang Le, Andrea Oversberg, Oliver Schaudt
The square of a graph , denoted by , is obtained from by putting an edge between two distinct vertices whenever their distance is two. Then is called a square root…
Better 3-coloring algorithms: excluding a triangle and a seven vertex path
Flavia Bonomo-Braberman, Maria Chudnovsky, Jan Goedgebeur +4
We present an algorithm to color a graph with no triangle and no induced -vertex path (i.e., a -free graph), where every vertex is assigned a list of possible c…
Partitioning two-coloured complete multipartite graphs into monochromatic paths and cycles
Oliver Schaudt, Maya Stein
We show that any complete -partite graph on vertices, with , whose edges are two-coloured, can be covered with two vertex-disjoint monochromatic paths of distin…
A new characterization of -free graphs
Eglantine Camby, Oliver Schaudt
The class of graphs that do not contain an induced path on vertices, -free graphs, plays a prominent role in algorithmic graph theory. This motivates the search for specia…
Structural parameterizations for boxicity
Henning Bruhn, Morgan Chopin, Felix Joos +1
The boxicity of a graph is the least integer such that has an intersection model of axis-aligned -dimensional boxes. Boxicity, the problem of deciding whether a give…