On the characterization of 3-tessellable graphs

Daniel Posner, Cauê F. Teixeira da Silva, Renato Portugal


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.


Diamond-free graphs, clique graph, line graph, graph tessellation, staggered quantum walk

Texto completo:


DOI: https://doi.org/10.5540/03.2018.006.02.0308


  • Não há apontamentos.

SBMAC - Sociedade de Matemática Aplicada e Computacional
Edifício Medical Center - Rua Maestro João Seppe, nº. 900, 16º. andar - Sala 163 | São Carlos/SP - CEP: 13561-120

Normas para publicação | Contato