19 citations · 69 across the 16 of their papers we have counts for
16 papers
Order 14 is the largest order for which every 4-total coloring of every cubic graph is equitable
Matheus Adauto, Celina de Figueiredo, Diana Sasaki +1
A total coloring of a graph is an assignment of colors to its vertices and edges so that adjacent or incident elements receive distinct colors, and it is equitable when the cardina…
The sandwich problem for odd-hole-free and even-hole-free graphs
Kathie Cameron, Aristotelis Chaniotis, Celina M. H. de Figueiredo +1
For a property of graphs, the -\textsc{Sandwich-Problem}, introduced by Golumbic and Shamir (1993), is the following: Given a pair of graphs …
An infinite family of Type 1 fullerene nanodiscs
Mariana da Cruz, Diane Castonguay, Celina de Figueiredo +1
A total coloring of a graph colors all its elements, vertices and edges, with no adjacency conflicts. The Total Coloring Conjecture (TCC) is a sixty year old challenge, says that e…
On the pebbling numbers of Flower, Blanuša, and Watkins snarks
Matheus Adauto, Celina de Figueiredo, Glenn Hurlbert +1
Graph pebbling is a game played on graphs with pebbles on their vertices. A pebbling move removes two pebbles from one vertex and places one pebble on an adjacent vertex. The pebbl…
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…
The graph tessellation cover number: extremal bounds, efficient algorithms and hardness
A. Abreu, L. Cunha, T. Fernandes +5
A tessellation of a graph is a partition of its vertices into vertex disjoint cliques. A tessellation cover of a graph is a set of tessellations that covers all of its edges. The $…
The tessellation problem of quantum walks
A. Abreu, L. Cunha, T. Fernandes +5
Quantum walks have received a great deal of attention recently because they can be used to develop new quantum algorithms and to simulate interesting quantum systems. In this work,…
Blind-friendly von Neumann's Heads or Tails
Vinícius Gusmão Pereira de Sá, Celina Miraglia Herrera de Figueiredo
The toss of a coin is usually regarded as the epitome of randomness, and has been used for ages as a means to resolve disputes in a simple, fair way. Perhaps as ancient as consulti…
Shifting coresets: obtaining linear-time approximations for unit disk graphs and other geometric intersection graphs
Guilherme D. da Fonseca, Vinícius G. Pereira de Sá, Celina M. H. de Figueiredo
Numerous approximation algorithms for problems on unit disk graphs have been proposed in the literature, exhibiting a sharp trade-off between running times and approximation ratios…
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…
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…
The Cost of Perfection for Matchings in Graphs
Emilio Vital Brazil, Guilherme D. da Fonseca, Celina de Figueiredo +1
Perfect matchings and maximum weight matchings are two fundamental combinatorial structures. We consider the ratio between the maximum weight of a perfect matching and the maximum…
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…