13 citations · 77 across the 56 of their papers we have counts for
14 papers · 1 filter
A rainbow partition theorem for trees and connected maximin share allocations of chores
Marcin Anholcer, Maciej Bartkowiak, Bartłomiej Bosek +3
Xiao, Qiu, and Huang (AAMAS 2023) and independently Lonc (personal communication) asked whether indivisible chores located at the vertices of a tree can always be allocated to …
Induced packing treewidth II. Excluding a clique or a biclique
Amir Nikabadi, Paweł Rzążewski
The notion of induced packing treewidth aims to unify classes defined by forbidden induced subgraphs or induced minors with classes defined by the existence of certain structured t…
Induced packing treewidth
Amir Nikabadi, Paweł Rzążewski
In this paper, we introduce a framework that aims to unify classes defined by forbidden induced subgraphs or induced minors with classes defined by the existence of certain structu…
Induced Erdős--Pósa property for long holes, long thetas, and beyond
Jadwiga Czyżewska, Tomáš Masařík, Marcin Pilipczuk +2
The induced Erdős--Pósa property in graphs relates the maximum number of pairwise anti-adjacent copies of an object with the minimum number of neighborhoods required to hit all cop…
Hitting all longest paths in -free graphs and -graphs
Paloma T. de Lima, Amir Nikabadi, Paweł Rzążewski
The \textit{longest path transversal number} of a connected graph , denoted by , is the minimum size of a set of vertices of that intersects all longest paths in …
List coloring ordered graphs with forbidden induced subgraphs
Marta Piecyk, Paweł Rzążewski
In the List -Coloring problem we are given a graph whose every vertex is equipped with a list, which is a subset of . We need to decide if admits a proper co…
Kernelization for list -coloring for graphs with small vertex cover
Marta Piecyk, Astrid Pieterse, Paweł Rzążewski +1
For a fixed graph , in the List -Coloring problem, we are given a graph along with list for every , and we have to determine if there ex…
On coarse tree decompositions and coarse balanced separators
Tara Abrishami, Jadwiga Czyżewska, Kacper Kluk +3
It is known that there is a linear dependence between the treewidth of a graph and its balanced separator number: the smallest integer such that for every weighing of the verti…
Excluding a clique or a biclique in graphs of bounded induced matching treewidth
Tara Abrishami, Marcin Briański, Jadwiga Czyżewska +4
For a tree decomposition of a graph , let denote the maximum size of an induced matching in with the property that some bag of c…
Minimal obstructions to -coloring in hereditary graph classes
Jan Goedgebeur, Jorik Jooken, Karolina Okrasa +2
For graphs and , an -coloring of is an edge-preserving mapping from to . Note that if is the triangle, then -colorings are equivalent to -color…
Every graph is eventually Turán-good
Natasha Morrison, JD Nir, Sergey Norin +2
Let be a graph. We show that if is large enough as a function of , then the -partite Turán graph maximizes the number of copies of among all -free graphs…
Computing homomorphisms in hereditary graph classes: the peculiar case of the 5-wheel and graphs with no long claws
Michał Dębski, Zbigniew Lonc, Karolina Okrasa +2
For graphs and , an -coloring of is an edge-preserving mapping from to . In the -Coloring problem the graph is fixed and we ask whether an instanc…
Taming graphs with no large creatures and skinny ladders
Jakub Gajarský, Lars Jaffke, Paloma T. Lima +4
We confirm a conjecture of Gartland and Lokshtanov [arXiv:2007.08761]: if for a hereditary graph class there exists a constant such that no member of $\mathcal{G}…
Coloring squares of planar graphs with small maximum degree
Mateusz Krzyziński, Paweł Rzążewski, Szymon Tur
For a graph , by we denote the minimum integer , such that there is a -coloring of the vertices of in which vertices at distance at most 2 receive distinct co…