12 citations · 18 across the 9 of their papers we have counts for
11 papers
Tree-independence number of -free graphs with no large bicliques
Václav Blažej, J. Pascal Gollin, Tomáš Hons +5
The tree-independence number of a graph is the minimum, over all tree-decompositions of the graph, of the maximum size of an independent set contained in a bag. Graph classes of bo…
Tree-independence number VII. Excluding a star
Maria Chudnovsky, Jadwiga Czyżewska, Marcin Pilipczuk +1
We prove that for every fixed integer and every planar graph , the class of -induced-minor-free and -induced-subgraph-free graphs has polylogarithmic tree-indepe…
Maximum Partial List H-Coloring on P_5-free graphs in polynomial time
Daniel Lokshtanov, Paweł Rzążewski, Saket Saurabh +2
In this article we show that Maximum Partial List H-Coloring is polynomial-time solvable on P_5-free graphs for every fixed graph H. In particular, this implies that Maximum k-Colo…
Odd Cycle Transversal on -free Graphs in Polynomial Time
Akanksha Agrawal, Paloma T. Lima, Daniel Lokshtanov +3
An independent set in a graph G is a set of pairwise non-adjacent vertices. A graph is bipartite if its vertex set can be partitioned into two independent sets. In the Odd Cycl…
Max Weight Independent Set in sparse graphs with no long claws
Tara Abrishami, Maria Chudnovsky, Cemil Dibek +2
We revisit the recent polynomial-time algorithm for the MAX WEIGHT INDEPENDENT SET (MWIS) problem in bounded-degree graphs that do not contain a fixed graph whose every component i…
Sparse induced subgraphs in P_6-free graphs
Maria Chudnovsky, Rose McCarty, Marcin Pilipczuk +2
We prove that a number of computational problems that ask for the largest sparse induced subgraph satisfying some property definable in CMSO2 logic, most notably Feedback Vertex Se…
Induced subgraphs and tree decompositions II. Toward walls and their line graphs in graphs of bounded degree
Tara Abrishami, Maria Chudnovsky, Cemil Dibek +4
This paper is motivated by the following question: what are the unavoidable induced subgraphs of graphs with large treewidth? Aboulker et al. made a conjecture which answers this q…
Polynomial-time algorithm for Maximum Independent Set in bounded-degree graphs with no long induced claws
Tara Abrishami, Maria Chudnovsky, Cemil Dibek +1
For graphs and , we say that is -free if it does not contain as an induced subgraph. Already in the early 1980s Alekseev observed that if is connected, then t…
Constant congestion brambles in directed graphs
Tomáš Masařík, Marcin Pilipczuk, Paweł Rzążewski +1
The Directed Grid Theorem, stating that there is a function such that a directed graphs of directed treewidth at least contains a directed grid of size at least as a…
Degeneracy of -free and -free graphs with no large complete bipartite subgraphs
Marthe Bonamy, Nicolas Bousquet, Michał Pilipczuk +3
A hereditary class of graphs is \emph{-bounded} if there exists a function such that every graph satisfies , where $χ(G)…
Exact Algorithm for Graph Homomorphism and Locally Injective Graph Homomorphism
Paweł Rzążewski
For graphs and , a homomorphism from to is a function , which maps vertices adjacent in to adjacent vertices of . A homomorphism is loc…