Total tessellation cover: bounds, hardness, and applications

DOI10.1016/J.DAM.2021.09.032MaRDI QIDQ2091795zbMATH OpenOpenAlexFDO

Authors Alexandre Abreu, Luís Felipe Ignácio Cunha, Franklin Marquezino, R. Portugal, C. 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

algorithms and complexitygraph coloringgraph tessellationquantum walks

Mathematics Subject Classification ID

Combinatorial aspects of tessellation and tiling problems (05B45) 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)

Recommendations

• The graph tessellation cover number: chromatic bounds, efficient algorithms and hardness
• The graph tessellation cover number: extremal bounds, efficient algorithms and hardness
• A computational complexity comparative study of graph tessellation problems
• Vertex and edge covers with clustering properties: Complexity and algorithms
• On complexity of total vertex cover on subcubic graphs

Cites work

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

Cited in

(5)

• On bounds for a board covering problem
• The graph tessellation cover number: chromatic bounds, efficient algorithms and hardness
• The graph tessellation cover number: extremal bounds, efficient algorithms and hardness
• Bounds and complexity for the tessellation problem
• \textsc{Tessellability} and \textsc{tessellability completion} of graphs with few \(P_4\)

Describes a project that uses

Uses Software

• CALMA

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

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