Paloma T. Lima

Postdoctoral researcher
University of Bergen, Norway

  Paloma [dot] Lima [at]
  Google Scholar

About me

I am currently a postdoctoral researcher in the Department of Computer Science of the University of Bergen.

My research interests lie mainly within structural graph theory, graph algorithms and parameterized complexity.

In November 2019, I completed my PhD at the University of Bergen, under the supervision of Pinar Heggernes. Before coming to Bergen, I did my masters and bachelor studies at the Federal University of Rio de Janeiro.


In proceedings of conferences (without a published journal version)       : open access

b-coloring parameterized by clique-width
with L. Jaffke and D. Lokshtanov
STACS 2021   |   arXiv

Three problems on well-partitioned chordal graphs
with J. Ahn, L. Jaffke and O. Kwon
CIAC 2021 (to appear)

Structural parameterizations of clique coloring
with L. Jaffke and G. Philip
MFCS 2020   |   arXiv

Algorithms for the rainbow vertex coloring problem on graph classes
with E. J. van Leeuwen and M. van der Wegen
MFCS 2020  |   arXiv

Well-partitioned chordal graphs: obstruction set and disjoint paths
with J. Ahn, L. Jaffke and O. Kwon
WG 2020  |   arXiv

Graph square roots of small distance from degree one graphs
with P. A. Golovach and C. Papadopoulos
LATIN 2020  |   arXiv

On the maximum number of edges in chordal graphs of bounded degree and matching number
with J. R. S. Blair, P. Heggernes and D. Lokshtanov
LATIN 2020

Rainbow vertex coloring bipartite graphs and chordal graphs
with P. Heggernes, D. Issac, J. Lauri and E. J. van Leeuwen
MFCS 2018 

Journal publications

Reducing graph transversals via edge contractions
with V. F. dos Santos, I. Sau and U. S. Souza
Journal of Computer and System Sciences (2021)   |   MFCS 2020
I wrote a short article about this paper for the Parameterized Complexity Newsletter.

Reducing the domination number of graphs via edge contractions and vertex deletions
with E. Galby and B. Ries
Discrete Mathematics (2021)    |   MFCS 2019 and ISAAC 2019  

Finding connected secluded subgraphs
with P. A. Golovach, P. Heggernes and P. Montealegre
Journal of Computer and System Sciences (2020)  |   IPEC 2017 

Parameterized aspects of strong subgraph closure
with P. A. Golovach, P. Heggernes, A. L. Konstantinidis and C. Papadopoulos
Algorithmica (2020)  |   SWAT 2018 

A complexity dichotomy for critical values of the b-chromatic number of graphs
with L. Jaffke
Theoretical Computer Science (2020)    |   MFCS 2019 

Intersection of longest paths in graph classes
with M. R. Cerioli
Discrete Applied Mathematics (2020)    |   CTW 2016

Transversals of longest paths
with M. R. Cerioli, C. G. Fernandes, R. Gómez and J. Gutiérrez
Discrete Mathematics (2020)  |   LAGOS 2017

Algorithms for outerplanar graph roots and graph roots of pathwidth at most 2
with P. A. Golovach, P. Heggernes, D. Kratsch and D. Paulusma
Algorithmica (2019)   |   WG 2017

Classifying k-edge colouring for H-free graphs
with E. Galby, D. Paulusma and B. Ries
Information Processing Letters (2019)


On the parameterized complexity of k-edge colouring (arXiv)
with E. Galby, D. Paulusma and B. Ries


Fall 2020

INF234 Algorithms: course material is available on Mitt UiB.

Academic service

I am a program committee member of ESA 2021

Since 2018, I regularly review papers for conferences (e.g. SODA, STACS, ESA, WG, MFCS, LATIN, IPEC) and journals (e.g. Journal of Graph Theory, SIAM Journal on Discrete Mathematics, Theoretical Computer Science, Information Processing Letters).