The Tessellation Cover Number of Good Tessellable Graphs

MaRDI QIDQ6324347zbMATH OpenFDO

Authors Alexandre Abreu, Luís Felipe Ignácio Cunha, Celina M. H. de Figueiredo, Luis Antonio B. Kowada, Franklin Marquezino, R. Portugal, Daniel F. D. Posner

Publication date 28 August 2019

Abstract: 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, and the tessellation cover number, denoted by $T(G)$, is the size of a smallest tessellation cover. The extsc{$t$-tessellability} problem aims to decide whether a graph $G$ has $T(G)leqt$ and is $mathcalNP$-complete for $tgeq3$. Since the number of edges of a maximum induced star of $G$, denoted by $is(G)$, is a lower bound on $T(G)$, we define good tessellable graphs as the graphs~$G$ such that $T(G)=is(G)$. The extsc{good tessellable recognition (gtr)} problem aims to decide whether $G$ is a good tessellable graph. We show that extsc{gtr} is $mathcalNP$-complete not only if $T(G)$ is known or $is(G)$ is fixed, but also when the gap between $T(G)$ and $is(G)$ is large. As a byproduct, we obtain graph classes that obey the corresponding computational complexity behaviors.

This page was built for publication: The Tessellation Cover Number of Good Tessellable Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6324347)