On the characterization of 3-tessellable graphs

Resumo

A graph tessellation is a partition of the vertices of the graph into cliques and a graph tessellation cover is a set of graph tessellations that covers the edges of the graph. A graph is 3-tessellable if it has a tessellation cover with three tessellations. The study of graph tessellations is important in quantum computation because the evolution operator of the staggered quantum walk model is obtained from a graph tessellation cover. In this work we establish a characterization on the smallest tessellation cover of a graph G using the chromatic number of its clique graph χ(K(G)) by showing that a diamond free graph G is 3-tessellable if and only if χ(K(G)) ≤ 4 and there is a vertex coloring assignment of K(G) with a special property. As a consequence of such characterization, we obtain a hardness proof for determining if a line graph of a triangle-free graph is 3-tessellable. Moreover, we introduce a special type of edge coloring of a triangle-free graph G which corresponds to a tessellation cover of its line graph. This hardness proof allows us to establish the N P -completeness of this new coloring problem for triangle-free graphs.