On the computational complexity of partial covers of theta graphs

DOI10.1016/j.dam.2007.05.051zbMath1138.05061OpenAlexW2025309825MaRDI QIDQ2482109

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)

Related Items (10)

An algorithmic framework for locally constrained homomorphisms ⋮ List covering of regular multigraphs with semi-edges ⋮ Locally constrained graph homomorphisms -- structure, complexity, and applications ⋮ Exact algorithm for graph homomorphism and locally injective graph homomorphism ⋮ Complexity of Locally Injective Homomorphism to the Theta Graphs ⋮ Locally Injective Homomorphism to the Simple Weight Graphs ⋮ Unnamed Item ⋮ The complexity of locally injective homomorphisms ⋮ Obstructions to locally injective oriented improper colourings ⋮ Locally constrained homomorphisms on graphs of bounded treewidth and bounded degree

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the complexity of H-coloring
• Role colouring a graph
• Covering regular graphs
• The NP-Completeness of Edge-Coloring
• Labelling Graphs with a Condition at Distance 2
• Graph labeling and radio channel assignment
• NP completeness of the edge precoloring extension problem on bipartite graphs
• Partial covers of graphs
• Fixed-parameter complexity of \(\lambda\)-labelings

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