Total tessellation cover: bounds, hardness, and applications

DOI10.1016/j.dam.2021.09.032zbMath1502.05197OpenAlexW3208343810MaRDI QIDQ2091795

Renato Portugal, Luís Cunha, Franklin Marquezino, Alexandre Abreu, Celina M. H. Figueiredo, Daniel F. D. Posner

Publication date: 2 November 2022

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2021.09.032

zbMATH Keywords

graph coloringquantum walksalgorithms and complexitygraph tessellation

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Structural characterization of families of graphs (05C75) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Combinatorial aspects of tessellation and tiling problems (05B45)

Uses Software

• CALMA

Cites Work

• Unnamed Item
• The staggered quantum walk model
• Total colorings and list total colorings of planar graphs without intersecting 4-cycles
• The ellipsoid method and its consequences in combinatorial optimization
• Total colouring regular bipartite graphs is NP-hard
• The NP-completeness of chromatic index in triangle free graphs with maximum vertex of degree 3
• The graph tessellation cover number: chromatic bounds, efficient algorithms and hardness
• A computational complexity comparative study of graph tessellation problems
• Chromatic index of graphs with no cycle with a unique chord
• New linear-time algorithms for edge-coloring planar graphs
• Implementation of quantum walks on IBM quantum computers
• Quantum walks and search algorithms
• Models and solution techniques for frequency assignment problems

This page was built for publication: Total tessellation cover: bounds, hardness, and applications