On the computational complexity of partial covers of theta graphs

DOI10.1016/J.DAM.2007.05.051MaRDI QIDQ2482109zbMATH OpenOpenAlexFDO

Authors Jan Kratochvíl, Attila Pór, Jiří Fiala

Publication date 16 April 2008

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

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

zbMATH Keywords

computational complexitygraph homomorphismstheta graphs

Mathematics Subject Classification ID

Structural characterization of families of graphs (05C75)

Recommendations

• scientific article; zbMATH DE number 2081019
• On the complexity of cover-incomparability graphs of posets
• Complexity of graph covering problems
• scientific article; zbMATH DE number 1236360
• Complexity results for well‐covered graphs
• scientific article; zbMATH DE number 89406
• On Tetha-graphs of partial cubes
• The complexity for the problems of covering of a graph with the minimum number of complete bipartite subgraphs
• The approximability of partial vertex covers in trees
• Covering of graphs by complete bipartite subgraphs; complexity of 0-1 matrices

Cites work

• Covering regular graphs
• Fixed-parameter complexity of \(\lambda\)-labelings
• Graph labeling and radio channel assignment
• scientific article; zbMATH DE number 91031 (Why is no real title available?)
• scientific article; zbMATH DE number 1236360 (Why is no real title available?)
• scientific article; zbMATH DE number 1033812 (Why is no real title available?)
• scientific article; zbMATH DE number 1107736 (Why is no real title available?)
• scientific article; zbMATH DE number 2038757 (Why is no real title available?)
• scientific article; zbMATH DE number 2080268 (Why is no real title available?)
• scientific article; zbMATH DE number 2081019 (Why is no real title available?)
• scientific article; zbMATH DE number 3445271 (Why is no real title available?)
• scientific article; zbMATH DE number 2117181 (Why is no real title available?)
• scientific article; zbMATH DE number 2197889 (Why is no real title available?)
• Labelling Graphs with a Condition at Distance 2
• NP completeness of the edge precoloring extension problem on bipartite graphs
• On the complexity of H-coloring
• Partial covers of graphs
• Role colouring a graph
• The NP-Completeness of Edge-Coloring

Cited in

(12)

• Locally constrained homomorphisms on graphs of bounded treewidth and bounded degree
• Exact algorithm for graph homomorphism and locally injective graph homomorphism
• Obstructions to locally injective oriented improper colourings
• Obstructions to injective oriented colourings
• Complexity of locally injective homomorphism to the Theta graphs
• Locally injective homomorphism to the simple weight graphs
• Locally constrained graph homomorphisms -- structure, complexity, and applications
• An algorithmic framework for locally constrained homomorphisms
• List covering of regular multigraphs with semi-edges
• An algorithmic framework for locally constrained homomorphisms
• Computational complexity of covering coloured mixed multigraphs with simple degree partitions
• The complexity of locally injective homomorphisms

This page was built for publication: On the computational complexity of partial covers of theta graphs

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