Topology

Unsolvability of word problem for 2-knot complements ★★★

Author(s): Gordon

Problem   Does there exist a smooth/PL embedding of $ S^2 $ in $ S^4 $ such that the fundamental group of the complement has an unsolvable word problem?

Keywords: 2-knot; Computational Complexity; knot theory

Posted by rybu
updated July 23rd, 2010
add new comment
Graph Theory » Coloring » Homomorphisms

Algorithm for graph homomorphisms ★★

Author(s): Fomin; Heggernes; Kratsch

Question  

Is there an algorithm that decides, for input graphs $ G $ and $ H $, whether there exists a homomorphism from $ G $ to $ H $ in time $ O(c^{|V(G)|+|V(H)|}) $ for some constant $ c $?

Keywords: algorithm; Exponential-time algorithm; homomorphism

Posted by jfoniok
updated July 8th, 2010
add new comment
Graph Theory

spanning trees ★★

Author(s):

Problem   Prove or disprove: Let $ G $ be a graph with the minimum vertex degree at least 2; that is, $ \delta(G)\geq 2 $. Then there exists a spanning tree $ T $ of $ G $ such that for every support vertex $ v $ in $ T $ if $ \deg_G(v)\geq 3 $, then $ \deg_T(v)\geq 3 $.

Keywords: spanning trees

Posted by akhodkar
updated May 20th, 2011
3 comments
Combinatorics

Transversal achievement game on a square grid ★★

Author(s): Erickson

Problem   Two players alternately write O's (first player) and X's (second player) in the unoccupied cells of an $ n \times n $ grid. The first player (if any) to occupy a set of $ n $ cells having no two cells in the same row or column is the winner. What is the outcome of the game given optimal play?

Keywords: game

Posted by Martin Erickson
updated January 6th, 2021
3 comments