Paper Info
Title
The graph tessellation cover number: Chromatic bounds, efficient algorithms and hardness.
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 is the size of the smallest tessellation cover. These concepts are motivated by their application to quantum walk models, in special, the evolution operator of the staggered model is obtained from a graph tessellation cover. We show that the minimum between the chromatic index of the graph and the chromatic number of its clique graph, which we call chromatic upper bound, is tight with respect to the tessellation cover number for star-octahedral and windmill graphs; whereas for (3,p)-extended wheel graphs, the tessellation cover number is 3 and the chromatic upper bound is 3p. The t-tessellability problem aims to decide whether there is a tessellation cover of the graph with t tessellations. Using graph classes whose tessellation cover numbers achieve the chromatic upper bound, we obtain that t-tessellability is polynomial-time solvable for bipartite, {triangle, proper major}-free, threshold, and diamond-free K-perfect graphs; whereas is NP-complete for triangle-free for t≥3, unichord-free for t≥3, planar for t=3, biplanar for t≥3, chordal (2,1)-graphs for t≥4, (1,2)-graphs for t≥4, and diamond-free with diameter at most five for t=3. We improve the complexity of 2-tessellability problem to linear time.
Year
DOI
Venue
2020
10.1016/j.tcs.2019.09.013
Theoretical Computer Science
Keywords
DocType
Volume
Graph tessellation cover,Graph coloring,Clique graph,Staggered quantum walk
Journal
801
ISSN
Citations 
PageRank 
0304-3975
0
0.34
References 
Authors
0
7
Name
Order
Citations
PageRank
A. Abreu100.34
Luís Felipe I. Cunha235.85
Celina M. H. de Figueiredo329638.49
Luis Antonio Brasil Kowada4239.01
F. L. Marquezino5196.66
Daniel Posner600.34
Renato Portugal75210.01