Karolina Okrasa

activity

20182026

most citedTuza's Conjecture for Threshold Graphs

2 citations · 3 across the 11 of their papers we have counts for

collaborators

Showing 2024Show all

3 papers · 1 filter

math.CO2024

Erdős-Pósa property of tripods in directed graphs

Marcin Briański, Meike Hatzel, Karolina Okrasa +1

Let $D$ be a directed graphs with distinguished sets of sources $S \subseteq V (D)$ and sinks $T \subseteq V (D)$ . A tripod in $D$ is a subgraph consisting of the union of two $S$ - $T$ -…

math.CO2024

Minimal obstructions to $C_{5}$ -coloring in hereditary graph classes

Jan Goedgebeur, Jorik Jooken, Karolina Okrasa +2

For graphs $G$ and $H$ , an $H$ -coloring of $G$ is an edge-preserving mapping from $V (G)$ to $V (H)$ . Note that if $H$ is the triangle, then $H$ -colorings are equivalent to $3$ -color…

cs.DS2024

Tree decompositions meet induced matchings: beyond Max Weight Independent Set

Paloma T. Lima, Martin Milanič, Peter Muršič +3

For a tree decomposition $T$ of a graph $G$ , by $μ (T)$ we denote the size of a largest induced matching in $G$ all of whose edges intersect one bag of $\mathcal…

Erdős-Pósa property of tripods in directed graphs

Minimal obstructions to C5​-coloring in hereditary graph classes

Tree decompositions meet induced matchings: beyond Max Weight Independent Set

Minimal obstructions to $C_{5}$ -coloring in hereditary graph classes