27 citations · 28 across the 9 of their papers we have counts for
Showing cs.CCShow all
3 papers · 1 filter
cs.CC2024
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…
cs.CC2023
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…
cs.CC2018★ 27 cited
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…