@article{ChandranIssacLaurietal.2022,
  author    = {Chandran, Sunil L. and Issac, Davis and Lauri, Juho and van Leeuwen, Erik Jan},
  title     = {Upper bounding rainbow connection number by forest number},
  series = {Discrete mathematics},
  volume    = {345},
  journal   = {Discrete mathematics},
  number    = {7},
  publisher = {Elsevier},
  address   = {Amsterdam [u.a.]},
  issn      = {0012-365X},
  doi       = {10.1016/j.disc.2022.112829},
  pages     = {22},
  year      = {2022},
  abstract  = {A path in an edge-colored graph is rainbow if no two edges of it are colored the same, and the graph is rainbow-connected if there is a rainbow path between each pair of its vertices. The minimum number of colors needed to rainbow-connect a graph G is the rainbow connection number of G, denoted by rc(G).\& nbsp;A simple way to rainbow-connect a graph G is to color the edges of a spanning tree with distinct colors and then re-use any of these colors to color the remaining edges of G. This proves that rc(G) <= |V (G)|-1. We ask whether there is a stronger connection between tree-like structures and rainbow coloring than that is implied by the above trivial argument. For instance, is it possible to find an upper bound of t(G)-1 for rc(G), where t(G) is the number of vertices in the largest induced tree of G? The answer turns out to be negative, as there are counter-examples that show that even c .t(G) is not an upper bound for rc(G) for any given constant c.\& nbsp;In this work we show that if we consider the forest number f(G), the number of vertices in a maximum induced forest of G, instead of t(G), then surprisingly we do get an upper bound. More specifically, we prove that rc(G) <= f(G) + 2. Our result indicates a stronger connection between rainbow connection and tree-like structures than that was suggested by the simple spanning tree based upper bound.},
  language  = {en}
}
@article{CaselDreierFernauetal.2020,
  author    = {Casel, Katrin and Dreier, Jan and Fernau, Henning and Gobbert, Moritz and Kuinke, Philipp and Villaamil, Fernando S{\´a}nchez and Schmid, Markus L. and van Leeuwen, Erik Jan},
  title     = {Complexity of independency and cliquy trees},
  series = {Discrete applied mathematics},
  volume    = {272},
  journal   = {Discrete applied mathematics},
  publisher = {Elsevier},
  address   = {Amsterdam [u.a.]},
  issn      = {0166-218X},
  doi       = {10.1016/j.dam.2018.08.011},
  pages     = {2 -- 15},
  year      = {2020},
  abstract  = {An independency (cliquy) tree of an n-vertex graph G is a spanning tree of G in which the set of leaves induces an independent set (clique). We study the problems of minimizing or maximizing the number of leaves of such trees, and fully characterize their parameterized complexity. We show that all four variants of deciding if an independency/cliquy tree with at least/most l leaves exists parameterized by l are either Para-NP- or W[1]-hard. We prove that minimizing the number of leaves of a cliquy tree parameterized by the number of internal vertices is Para-NP-hard too. However, we show that minimizing the number of leaves of an independency tree parameterized by the number k of internal vertices has an O*(4(k))-time algorithm and a 2k vertex kernel. Moreover, we prove that maximizing the number of leaves of an independency/cliquy tree parameterized by the number k of internal vertices both have an O*(18(k))-time algorithm and an O(k 2(k)) vertex kernel, but no polynomial kernel unless the polynomial hierarchy collapses to the third level. Finally, we present an O(3(n) . f(n))-time algorithm to find a spanning tree where the leaf set has a property that can be decided in f (n) time and has minimum or maximum size.},
  language  = {en}
}