A computational complexity comparative study of graph tessellation problems

A tessellation of a graph is a partition of its vertices into cliques. A tessellation cover of a graph is a set of tessellations that covers all of its edges, and the tessellation cover number, denoted by T(G), is the size of a smallest tessellation cover. The t-TESSELLABILITy problem aims to decide whether a graph G has T(G) <= t. The number of edges of a maximum induced star of G, denoted by s(G), is a lower bound on T(G). In this work we define good tessellable graphs as the graphs G with T(G) = s(G), and we introduce the corresponding gOOd TESSELLABLE RECOgNITION (gTR) problem, which aims to decide whether G is a good tessellable graph. We show that gTR is NP-complete not only if T(G) can be obtained in polynomial time or s(G) is fixed, but also when the gap between T(G) and s(G) is large. We establish graph classes that present distinct computational complexities considering problems related to the parameters T(G) and s(G), and we perform a comparative study of the gTR, t-TESSELLABILITy, and STAR SIzE problems, where the STAR SIzE problem aims to decide whether the number of edges a maximum induced star of a graph is at least a given number. (c) 2020 Elsevier B.V. All rights reserved.