15 citations · 15 across the 2 of their papers we have counts for
4 papers
Complexity of fall coloring for restricted graph classes
Juho Lauri, Christodoulos Mitillos
We strengthen a result by Laskar and Lyle (Discrete Appl. Math. (2009), 330-338) by proving that it is NP-complete to decide whether a bipartite planar graph can be partitioned int…
Algorithms and hardness results for happy coloring problems
N. R. Aravind, Subrahmanyam Kalyanasundaram, Anjeneya Swami Kare +1
In a vertex-colored graph, an edge is happy if its endpoints have the same color. Similarly, a vertex is happy if all its incident edges are happy. Motivated by the computation of…
The square of the 9-hypercube is 14-colorable
Juho Lauri
The -hypercube, denoted by , has a vertex for each bit string of length with two vertices adjacent whenever their Hamming distance is one. The minimum number of colors…
On the fine-grained complexity of rainbow coloring
Łukasz Kowalik, Juho Lauri, Arkadiusz Socała
The Rainbow k-Coloring problem asks whether the edges of a given graph can be colored in colors so that every pair of vertices is connected by a rainbow path, i.e., a path with…