1 citations · 1 across the 6 of their papers we have counts for
6 papers
Burling graphs in graphs with large chromatic number
Tara Abrishami, Marcin Briański, James Davies +4
A graph class is -bounded if the only way to force large chromatic number in graphs from the class is by forming a large clique. In the 1970s, Erdős conjectured that intersectio…
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 …
Tabular intermediate logics comparison
Paweł Rzążewski, Michał Stronkowski
Tabular intermediate logics are intermediate logics characterized by finite posets treated as Kripke frames. For a poset , let denote the corresponding…
Finding large -colorable induced subgraphs in (bull, chair)-free and (bull,E)-free graphs
Nadzieja Hodur, Monika Pilśniak, Magdalena Prorok +1
We study the Max Partial -Coloring problem, where we are given a vertex-weighted graph, and we ask for a maximum-weight induced subgraph that admits a proper -coloring. For $…
Fundamental Problems on Bounded-Treewidth Graphs: The Real Source of Hardness
Barış Can Esmer, Jacob Focke, Dániel Marx +1
It is known for many algorithmic problems that if a tree decomposition of width is given in the input, then the problem can be solved with exponential dependence on . A line…
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…