8 citations · 51 across the 26 of their papers we have counts for
4 papers · 2 filters
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…
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…
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…