19 citations · 69 across the 16 of their papers we have counts for
5 papers · 1 filter
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,…
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…
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…