The graph tessellation cover number: chromatic bounds, efficient algorithms and hardness

DOI10.1016/J.TCS.2019.09.013zbMATH Open1442.05168arXiv1705.09014OpenAlexW2778913481MaRDI QIDQ2007724FDOQ2007724

Authors: Yanyan Li 

Publication date: 22 November 2019

Published in: Theoretical Computer Science (Search for Journal in Brave)

Abstract: Quantum walks have received a great deal of attention recently because they can be used to develop new quantum algorithms and to simulate interesting quantum systems. In this work, we focus on a model called staggered quantum walk, which employs advanced ideas of graph theory and has the advantage of including the most important instances of other discrete-time models. The evolution operator of the staggered model is obtained from a tessellation cover, which is defined in terms of a set of partitions of the graph into cliques. It is important to establish the minimum number of tessellations required in a tessellation cover, and what classes of graphs admit a small number of tessellations. We describe two main results: (1) infinite classes of graphs where we relate the chromatic number of the clique graph to the minimum number of tessellations required in a tessellation cover, and (2) the problem of deciding whether a graph is $k$-tessellable for $kge3$ is NP-complete.

Full work available at URL: https://arxiv.org/abs/1705.09014

Recommendations

• The graph tessellation cover number: extremal bounds, efficient algorithms and hardness
• Total tessellation cover: bounds, hardness, and applications
• Graph covers using \(t\)-colourable vertex sets.
• The chromatic covering number of a graph
• Publication:4484774
• Bounding cochordal cover number of graphs via vertex stretching
• The k‐path vertex cover: General bounds and chordal graphs
• The complexity of the cover polynomials for planar graphs of bounded degree
• Covering and tiling hypergraphs with tight cycles
• Covering and tiling hypergraphs with tight cycles

zbMATH Keywords

graph coloringstaggered quantum walkclique graphgraph tessellation cover

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Coloring of graphs and hypergraphs (05C15) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• Title not available (Why is that?)
• Geometric algorithms and combinatorial optimization
• Quantum walks: a comprehensive review
• Algorithmic graph theory and perfect graphs
• Threshold graphs and related topics
• A \(max \{m, n \}\) algorithm for determining the graph H from its line graph G
• The staggered quantum walk model
• Vertex domination-critical graphs
• Title not available (Why is that?)
• Planar graphs of maximum degree seven are Class I
• NP completeness of finding the chromatic index of regular graphs
• Title not available (Why is that?)
• NP-completeness of edge-colouring some restricted graphs
• Chromatic index of graphs with no cycle with a unique chord
• On clique-perfect and K-perfect graphs
• The icosahedron is clique divergent
• The NP-completeness of chromatic index in triangle free graphs with maximum vertex of degree 3
• Partition-based discrete-time quantum walks
• Gridline graphs: A review in two dimensions and an extension to higher dimensions
• The graph tessellation cover number: extremal bounds, efficient algorithms and hardness
• Title not available (Why is that?)

Cited In (5)

• A computational complexity comparative study of graph tessellation problems
• Title not available (Why is that?)
• Total tessellation cover: bounds, hardness, and applications
• Walking on vertices and edges by continuous-time quantum walk
• Implementation of quantum walks on IBM quantum computers

This page was built for publication: The graph tessellation cover number: chromatic bounds, efficient algorithms and hardness

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