27 citations · 28 across the 9 of their papers we have counts for
9 papers
The parameterized complexity of Strong Conflict-Free Vertex-Connection Colorability
Carl Feghali, Hoang-Oanh Le, Van Bang Le
This paper continues the study of a new variant of graph coloring with a connectivity constraint recently introduced by Hsieh et al. [COCOON 2024]. A path in a vertex-colored graph…
The complexity of strong conflict-free vertex-connection -colorability
Sun-Yuan Hsieh, Hoang-Oanh Le, Van Bang Le +1
We study a new variant of graph coloring by adding a connectivity constraint. A path in a vertex-colored graph is called conflict-free if there is a color that appears exactly once…
Complexity of the (Connected) Cluster Vertex Deletion problem on -free graphs
Hoang-Oanh Le, Van Bang Le
The well-known Cluster Vertex Deletion problem (CVD) asks for a given graph and an integer whether it is possible to delete a set of at most vertices of such th…
Complexity and algorithms for matching cut problems in graphs without long induced paths and cycles
Hoang-Oanh Le, Van Bang Le
In a graph, a (perfect) matching cut is an edge cut that is a (perfect) matching. Matching Cut (MC), respectively, Perfect Matching Cut (PMC), is the problem of deciding whether a…
On the -Claw Vertex Deletion Problem
Sun-Yuan Hsieh, Hoang-Oanh Le, Van Bang Le +1
Let -claw (or -star) stand for , the complete bipartite graph with 1 and vertices on each part. The -claw vertex deletion problem, -CLAW-VD, asks for…
Map graphs having witnesses of large girth
Hoang-Oanh Le, Van Bang Le
A half-square of a bipartite graph has one color class of as vertex set, say ; two vertices are adjacent whenever they have a common neighbor in . If $G=(V,…
Hardness and structural results for half-squares of restricted tree convex bipartite graphs
Hoang-Oanh Le, Van Bang Le
Let be a bipartite graph. A half-square of has one color class of as vertex set, say ; two vertices are adjacent whenever they have a common neighbor in .…
A complexity dichotomy for Matching Cut in (bipartite) graphs of fixed diameter
Hoang-Oanh Le, Van Bang Le
In a graph, a matching cut is an edge cut that is a matching. Matching Cut is the problem of deciding whether or not a given graph has a matching cut, which is known to be NP-compl…
Tropical Vertex-Disjoint Cycles of a Vertex-Colored Digraph: Barter Exchange with Multiple Items Per Agent
Timothy Highley, Hoang Le
In a barter exchange market, agents bring items and seek to exchange their items with one another. Agents may agree to a k-way exchange involving a cycle of k agents. A barter exch…