1 citations · 1 across the 11 of their papers we have counts for
8 papers · 1 filter
Odd Cycle Transversal on -free graphs
Esther Galby, Paloma T. de Lima, Andrea Munaro +1
\textsc{Odd Cycle Transversal} is a classic -hard graph optimization problem asking for a minimum-weight set of vertices whose deletion makes the input graph bipartite…
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…
A Dense Weisfeiler-Leman Algorithm for Deciding Bounded-Cliquewidth Homomorphism Indistinguishability
Radu Curticapean, Daniel Neuen, Amir Nikabadi +2
Two graphs and are homomorphism indistinguishable over a graph class if they admit the same number of homomorphisms from every graph in . A wide…
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…
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…
The Gallai Vertex Problem is -Complete
Amir Nikabadi, Eva Rotenberg, Lasse Wulf
When a graph admits a vertex that is contained in all its longest paths, we call a Gallai vertex. These are named after Gallai, who in 1966 asked the question if it is…
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…