18 papers
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…
Sparse induced subgraphs in -free graphs of bounded clique number
Maria Chudnovsky, Jadwiga Czyżewska, Kacper Kluk +2
Many natural computational problems, including e.g. Max Weight Independent Set, Feedback Vertex Set, or Vertex Planarization, can be unified under an umbrella of finding the larges…
Clique-width and induced topological minors
PaweÅ RafaÅ BieliÅski, Jadwiga Czyżewska, Martin MilaniÄ +2
A is a chordless path on four vertices. A diamond is a graph obtained from a clique of size four by removing one edge of the clique. A paw is a graph obtained from a clique o…
Maximum Weight Independent Set in Hereditary Classes of Ordered Graphs
PaweÅ RafaÅ BieliÅski, Marta Piecyk, PaweÅ RzÄ Å¼ewski
The complexity of classical computational problems in graph classes defined by forbidding induced subgraphs is one of the central topics of algorithmic graph theory. Recently, ther…
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…
Finding large sparse induced subgraphs in graphs of small (but not very small) tree-independence number
Daniel Lokshtanov, MichaÅ Pilipczuk, PaweÅ RzÄ Å¼ewski
The independence number of a tree decomposition is the size of a largest independent set contained in a single bag. The tree-independence number of a graph is the minimum indep…