4 citations · 13 across the 17 of their papers we have counts for
6 papers · 1 filter
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…
Metric Dimension and Geodetic Set Parameterized by Vertex Cover
Florent Foucaud, Esther Galby, Liana Khazaliya +4
For a graph , a subset is called a resolving set of if, for any two vertices , there exists a vertex such that . T…
Eliminating Crossings in Ordered Graphs
Akanksha Agrawal, Sergio Cabello, Michael Kaufmann +4
Drawing a graph in the plane with as few crossings as possible is one of the central problems in graph drawing and computational geometry. Another option is to remove the smallest…
Balanced Substructures in Bicolored Graphs
P. S. Ardra, R. Krithika, Saket Saurabh +1
An edge-colored graph is said to be balanced if it has an equal number of edges of each color. Given a graph whose edges are colored using two colors and a positive integer …
Hitting Meets Packing: How Hard Can it Be?
Jacob Focke, Fabian Frei, Shaohua Li +4
We study a general family of problems that form a common generalization of classic hitting (also referred to as covering or transversal) and packing problems. An instance of X-HitP…
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…