4 papers · 1 filter
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…
On Cycle Transversals and Their Connected Variants in the Absence of a Small Linear Forest
Konrad K. Dabrowski, Carl Feghali, Matthew Johnson +3
A graph is -free if it contains no induced subgraph isomorphic to . We prove new complexity results for the two classical cycle transversal problems Feedback Vertex Set and O…
Independent Feedback Vertex Set for -free Graphs
Marthe Bonamy, Konrad K. Dabrowski, Carl Feghali +2
The NP-complete problem Feedback Vertex Set is that of deciding whether or not it is possible, for a given integer , to delete at most vertices from a given graph so t…
Independent Feedback Vertex Sets for Graphs of Bounded Diameter
Marthe Bonamy, Konrad K. Dabrowski, Carl Feghali +2
The Near-Bipartiteness problem is that of deciding whether or not the vertices of a graph can be partitioned into sets and , where is an independent set and induces…