The Graph Tessellation Cover Number: Extremal Bounds, Efficient Algorithms and Hardness
| Autor: | Franklin de Lima Marquezino, Luis Antonio Brasil Kowada, Renato Portugal, Celina M. H. de Figueiredo, Daniel Posner, Luís Felipe I. Cunha, Tharso D. Fernandes, Alexandre Santiago de Abreu |
|---|---|
| Rok vydání: | 2018 |
| Předmět: |
Tessellation
0102 computer and information sciences Disjoint sets Computer Science::Computational Geometry Clique graph 01 natural sciences Vertex (geometry) Planar graph Combinatorics Edge coloring symbols.namesake 010201 computation theory & mathematics Chordal graph 0103 physical sciences symbols Quantum walk 010306 general physics Mathematics |
| Zdroj: | LATIN 2018: Theoretical Informatics ISBN: 9783319774039 LATIN |
| DOI: | 10.1007/978-3-319-77404-6_1 |
| Popis: | 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. The t-tessellability problem aims to decide whether there is a tessellation cover of the graph with t tessellations. This problem is motivated by its applications to quantum walk models, in especial, the evolution operator of the staggered model is obtained from a graph tessellation cover. We establish upper bounds on the tessellation cover number given by the minimum between the chromatic index of the graph and the chromatic number of its clique graph and we show graph classes for which these bounds are tight. We prove \(\mathcal {NP}\)-completeness for t-tessellability if the instance is restricted to planar graphs, chordal (2, 1)-graphs, (1, 2)-graphs, diamond-free graphs with diameter five, or for any fixed t at least 3. On the other hand, we improve the complexity for 2-tessellability to a linear-time algorithm. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|