19 citations · 50 across the 7 of their papers we have counts for
7 papers
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 …
Complexity of colouring problems restricted to unichord-free and \{square,unichord\}-free graphs
Raphael C. S. Machado, Celina M. H. de Figueiredo, Nicolas Trotignon
A \emph{unichord} in a graph is an edge that is the unique chord of a cycle. A \emph{square} is an induced cycle on four vertices. A graph is \emph{unichord-free} if none of its ed…
Edge-colouring and total-colouring chordless graphs
Raphael C. S. Machado, Celina M. H. de Figueiredo, Nicolas Trotignon
A graph is \emph{chordless} if no cycle in has a chord. In the present work we investigate the chromatic index and total chromatic number of chordless graphs. We describe a…
Complements of nearly perfect graphs
András Gyárfás, Zhentao Li, Raphael Machado +3
A class of graphs closed under taking induced subgraphs is -bounded if there exists a function such that for all graphs in the class, . We consider th…
Efficient sub-5 approximations for minimum dominating sets in unit disk graphs
Guilherme D. da Fonseca, Celina M. H. de Figueiredo, Vinícius G. P. de Sá +1
A unit disk graph is the intersection graph of n congruent disks in the plane. Dominating sets in unit disk graphs are widely studied due to their application in wireless ad-hoc ne…
Biclique-colouring verification complexity and biclique-colouring power graphs
Hélio B. Macêdo Filho, Simone Dantas, Raphael C. S. Machado +1
Biclique-colouring is a colouring of the vertices of a graph in such a way that no maximal complete bipartite subgraph with at least one edge is monochromatic. We show that it is c…
Complexity dichotomy on partial grid recognition
Vinícius G. P. de Sá, Guilherme D. da Fonseca, Raphael Machado +1
Deciding whether a graph can be embedded in a grid using only unit-length edges is NP-complete, even when restricted to binary trees. However, it is not difficult to devise a numbe…