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

DOI10.1016/J.TCS.2019.09.013MaRDI QIDQ2007724zbMATH OpenOpenAlexFDO

Authors Yanyan Li

Publication date 22 November 2019

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

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

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)

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.

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

Cites work

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

Cited in

(8)

• A computational complexity comparative study of graph tessellation problems
• The graph tessellation cover number: extremal bounds, efficient algorithms and hardness
• Implementation of quantum walks on IBM quantum computers
• Bounds and complexity for the tessellation problem
• \textsc{Tessellability} and \textsc{tessellability completion} of graphs with few \(P_4\)
• Total tessellation cover: bounds, hardness, and applications
• scientific article; zbMATH DE number 7453155 (Why is no real title available?)
• Walking on vertices and edges by continuous-time quantum walk

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)