4 papers
MaxCut on Permutation Graphs is NP-complete
Celina M. H. de Figueiredo, Alexsander A. de Melo, Fabiano S. Oliveira +1
In this paper, we prove that the MaxCut problem is NP-complete on permutation graphs, settling a long-standing open problem that appeared in the 1985 column of the "Ongoing Guide t…
Most direct product of graphs are Type 1
Diane Castonguay, Celina M. H. de Figueiredo, Luis Antonio Kowada +2
A \textit{-total coloring} of a graph is an assignment of colors to its elements (vertices and edges) so that adjacent or incident elements have different colors. The to…
Revising Johnson's table for the 21st century
Celina M. H. de Figueiredo, Alexsander A. de Melo, Diana Sasaki +1
What does it mean today to study a problem from a computational point of view? We focus on parameterized complexity and on Column 16 "Graph Restrictions and Their Effect" of D. S.…
Transitive orientations in bull-reducible Berge graphs
Celina de Figueiredo, Frederic Maffray, Claudia Villela Maciel
A bull is a graph with five vertices and five edges , , , , . A graph is bull-reducible if no vertex of lies in two bulls. We prove that…