6 papers · 1 filter
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…
Counting equitable -colorings in graphs of bounded clique-width
Holger Dell, Thore Husfeldt, Amir Nikabadi
For a graph , a proper -coloring of is \emph{equitable} if the sizes of any two color classes differ by at most one. The \textsc{Equitable -Coloring} problem asks, for…
Equitable coloring of large bipartite graphs
Amir Nikabadi
For a graph , the \emph{equitable chromatic number} of , denoted by , is the smallest integer such that admits a proper -coloring whose color classes diffe…
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 …
Maximum list -colorable induced subgraphs in -free graphs
Esther Galby, Paloma T. Lima, Andrea Munaro +1
We show that, for every fixed positive integers and , \textsc{Max-Weight List -Colorable Induced Subgraph} admits a polynomial-time algorithm on -free graphs. This…
Non-empty intersection of longest paths in -free and claw-free graphs
Paloma T. Lima, Amir Nikabadi
A family of graphs is a \textit{Gallai family} if for every connected graph , all longest paths in have a common vertex. While it is not known w…