19 citations · 69 across the 16 of their papers we have counts for
Showing cs.CCShow all
2 papers · 1 filter
cs.CC2020
Maximum cut on interval graphs of interval count four is NP-complete
Celina M. H. de Figueiredo, Alexsander A. de Melo, Fabiano S. Oliveira +1
The computational complexity of the MaxCut problem restricted to interval graphs has been open since the 80's, being one of the problems proposed by Johnson on his Ongoing Guide to…
cs.CC2013
Hierarchical complexity of 2-clique-colouring weakly chordal graphs and perfect graphs having cliques of size at least 3
Hélio B. Macêdo Filho, Raphael C. S. Machado, Celina M. H. de Figueiredo
A clique of a graph is a maximal set of vertices of size at least 2 that induces a complete graph. A -clique-colouring of a graph is a colouring of the vertices with at most …