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,…